Find the k-th lexicographically smallest happy string of length n, or return an empty string if fewer than k exist.
Given two integers and , consider all happy strings of length formed using only the letters a, b, and c.
A string is happy if no two adjacent characters are the same.
Your task is to return the -th string in lexicographical order among all happy strings of length . If there are fewer than such strings, return an empty string.
A string s is lexicographically smaller than string t if at the first position where they differ, the character in s comes before the character in t alphabetically.
Input Format
Input
- Two integers
nandk.
Interpretation
nis the required length of the happy string.kis 1-indexed and refers to the lexicographical rank among all valid strings.
Output Format
Output
- Return the -th lexicographically smallest happy string of length
n. - If it does not exist, return an empty string
"".
Constraints
- Only characters
a,b, andcmay be used. - Adjacent characters in the string must always be different.
Example 1
Input
n = 1, k = 3
Output
c
Explanation
The happy strings of length 1 in order are: a, b, c. The 3rd one is c.
Example 2
Input
n = 3, k = 9
Output
cab
Explanation
The happy strings of length 3 in lexicographical order are:
aba, abc, aca, acb, bab, bac, bca, bcb, cab, cac, cba, cbc.
The 9th string is cab.
Show 1 more example
Example 3
Input
n = 3, k = 13
Output
Explanation
There are only 12 happy strings of length 3, so the 13th does not exist.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.