The k-th Lexicographical String of All Happy Strings of Length n

Medium
1294.

The k-th Lexicographical String of All Happy Strings of Length n

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.

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 <= 10
  • 1 <= k <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getHappyString = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 10
  • 1 <= k <= 100

Hints for The k-th Lexicographical String of All Happy Strings of Length n

  1. Hint 1

    How many happy strings of length n are there? The first letter has 3 choices and every later letter has 2.

  2. Hint 2

    So there are 3 * 2^(n-1) strings; if k is larger, the answer is empty. Otherwise the first letter splits the list into three equal blocks of 2^(n-1).

  3. Hint 3

    Fix the letters one at a time: at each later position the two allowed letters split the remaining block in half, and k tells you which half (like reading the bits of k - 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

  1. If k > 3 * 2^(n-1), return the empty string.
  2. Set k = k - 1 (0-based) and block = 2^(n-1). The first letter is "abc"[k / block]; set k %= block.
  3. For each next position: halve block, list the two letters different from the previous one in alphabetical order, take the one at index k / block, and set k %= block.
  4. 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 k exceeds 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