The k-th Lexicographical String of All Happy Strings of Length n
The k-th Lexicographical String of All Happy Strings of Length n solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
The k-th Lexicographical String of All Happy Strings of Length n is a medium coding problem on strings, backtracking and combinatorics, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Strings, Backtracking, Combinatorics
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string is happy if it uses only the letters 'a', 'b' and 'c', and no two neighbouring characters are equal. For example "abc", "ac" and "b" are happy, while "aa", "baa" and "ababbc" are not.
List all happy strings of length n in lexicographical (dictionary) order. Return the k-th string of that list (counting from 1), or an empty string if the list has fewer than k strings.
Example 1
Input: n = 1, k = 3
Output: "c"
Explanation: The list is ["a", "b", "c"].
Example 2
Input: n = 1, k = 4
Output: ""
Explanation: There are only three happy strings of length 1.
Example 3
Input: n = 3, k = 9
Output: "cab"
Explanation: The list is ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"].
Constraints
1 <= n <= 101 <= k <= 100
Hints for The k-th Lexicographical String of All Happy Strings of Length n
Hint 1
How many happy strings of length
nare there? The first letter has 3 choices and every later letter has 2.Hint 2
So there are
3 * 2^(n-1)strings; ifkis larger, the answer is empty. Otherwise the first letter splits the list into three equal blocks of2^(n-1).Hint 3
Fix the letters one at a time: at each later position the two allowed letters split the remaining block in half, and
ktells you which half (like reading the bits ofk - 1).
How to solve The k-th Lexicographical String of All Happy Strings of Length n
The happy strings in order form a complete tree — 3 children at the root, 2 everywhere else — so the k-th leaf can be found by division, without listing anything.
Approach
- If
k > 3 * 2^(n-1), return the empty string. - Set
k = k - 1(0-based) andblock = 2^(n-1). The first letter is"abc"[k / block]; setk %= block. - For each next position: halve
block, list the two letters different from the previous one in alphabetical order, take the one at indexk / block, and setk %= block. - Return the built string.
Why it works
Sorting the happy strings lexicographically groups them by first letter into three equal blocks of 2^(n-1), and inside a block by second letter into two equal halves, and so on. The 0-based index k therefore decomposes as first * 2^(n-1) + second * 2^(n-2) + …, which is exactly what repeated division and remainder extract.
Complexity
- Time —
O(n) - Space —
O(n) for the answer
Pitfalls
- Forgetting the empty-string case when
kexceeds the number of happy strings. - The two choices after a letter must be taken in alphabetical order — after
'b'they are'a'then'c'. - Generating all strings by backtracking also works for these limits, but it is exponential in
n.
Reference solution
Python
def getHappyString(n: int, k: int) -> str:
block = 1 << (n - 1)
if k > 3 * block:
return ""
k -= 1
res = ["abc"[k // block]]
k %= block
for _ in range(1, n):
block //= 2
options = [c for c in "abc" if c != res[-1]]
res.append(options[k // block])
k %= block
return "".join(res)Java
public static String getHappyString(int n, int k) {
int block = 1 << (n - 1);
if (k > 3 * block) return "";
k--;
StringBuilder res = new StringBuilder();
res.append((char) ('a' + k / block));
k %= block;
for (int i = 1; i < n; i++) {
block >>= 1;
char last = res.charAt(i - 1);
char[] options = new char[2];
int m = 0;
for (char c = 'a'; c <= 'c'; c++) if (c != last) options[m++] = c;
res.append(options[k / block]);
k %= block;
}
return res.toString();
}C++
string getHappyString(int n, int k) {
int block = 1 << (n - 1);
if (k > 3 * block) return "";
k--;
string res(1, (char)('a' + k / block));
k %= block;
for (int i = 1; i < n; i++) {
block >>= 1;
char options[2];
int m = 0;
for (char c = 'a'; c <= 'c'; c++) if (c != res.back()) options[m++] = c;
res += options[k / block];
k %= block;
}
return res;
}JavaScript
var getHappyString = function(n, k) {
var block = 1 << (n - 1);
if (k > 3 * block) return "";
k--;
var res = "abc"[Math.floor(k / block)];
k %= block;
for (var i = 1; i < n; i++) {
block >>= 1;
var last = res[res.length - 1];
var options = [];
for (var j = 0; j < 3; j++) if ("abc"[j] !== last) options.push("abc"[j]);
res += options[Math.floor(k / block)];
k %= block;
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Backtracking