643. Kth Cheerful String
Call a string cheerful if it uses only the letters p, q and r and no two neighbouring letters are equal. List all cheerful strings of length n in dictionary (alphabetical) order. Return the k-th string of that list (counting from 1), or the empty string if there are fewer than k cheerful strings of length n.
Example 1
- Input:
- n = 2, k = 4
- Output:
- "qr"
- Explanation:
The cheerful strings of length 2 in order are pq, pr, qp, qr, rp, rq. The fourth is
qr.
Example 2
- Input:
- n = 3, k = 9
- Output:
- "rpq"
- Explanation:
Of the 12 strings of length 3 (pqp, pqr, prp, prq, qpq, qpr, qrp, qrq, rpq, rpr, rqp, rqr), the ninth is
rpq.
Example 3
- Input:
- n = 1, k = 4
- Output:
- ""
- Explanation:
There are only three strings of length 1, so the answer is the empty string.
Constraints
- 1 ≤
n≤ 30 - 1 ≤
k≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)