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

Problem

A happy string is a string that:

• consists only of letters of the set ['a', 'b', 'c'].
• s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).

For example, strings “abc”, “ac”, “b” and “abcbabcbcb” are all happy strings and strings “aa”, “baa” and “ababbc” are not happy strings.

Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.

Return the kth string of this list or return an empty string if there are less than k happy strings of length n.]()

Examples

Example 1:

1
2
3

Input: n = 1, k = 3
Output: "c"
Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c".

Example 2:

1
2
3

Input: n = 1, k = 4
Output: ""
Explanation: There are only 3 happy strings of length 1.

Example 3:

1
2
3

Input: n = 3, k = 9
Output: "cab"
Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab"

Constraints:

• 1 <= n <= 10
• 1 <= k <= 100

Solution

Method 1 - Backtracking

The goal is to generate all “happy strings” of length n, sort them lexicographically, and return the kth string. A “happy string” adheres to the following rules:

1. It contains only the characters ['a', 'b', 'c'].
2. Consecutive characters are different.

Given the constraints, generating all strings using recursion is a suitable approach. Using backtracking, we’ll attempt to build strings character by character, ensuring they are “happy” at every step. Once we have all happy strings, we can access the kth string directly or return an empty string if k exceeds the count.

Approach

1. Backtracking: Start with an empty string and try appending each character ['a', 'b', 'c'], ensuring no two consecutive characters are the same.
2. Base Case: Stop when the string reaches the desired length n, and add it to a result array.
3. Lexicographical Order: Backtracking naturally produces strings in lexicographical order due to the order of character choices.
4. Check if the number of generated happy strings is at least k. If yes, return the kth string; otherwise, return an empty string.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public String getHappyString(int n, int k) {
        List<String> ans = new ArrayList<>();  // Using ans instead of res
        StringBuilder curr = new StringBuilder();  // Replace String with StringBuilder
        backtrack(n, curr, ans);
        return k <= ans.size() ? ans.get(k - 1) : "";
    }
    
    private void backtrack(int n, StringBuilder curr, List<String> ans) {
        if (curr.length() == n) {  // Base case: Valid happy string of length n
            ans.add(curr.toString());  // Convert StringBuilder to String and add to ans
            return;
        }
        
        for (char ch : new char[] {'a', 'b', 'c'}) {  // Using ch instead of c for clarity
            if (curr.length() == 0 || curr.charAt(curr.length() - 1) != ch) {  // No consecutive identical chars
                curr.append(ch);  // Add to StringBuilder
                backtrack(n, curr, ans);  // Recurse
                curr.deleteCharAt(curr.length() - 1);  // Undo the change (backtrack)
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public String getHappyString(int n, int k) {
        List<String> ans = new ArrayList<>();
        backtrack("", n, ans);
        return k <= res.size() ? res.get(k - 1) : "";
    }
    
    private void backtrack(String curr, int n, List<String> ans) {
        if (curr.length() == n) {  // Base case: Valid happy string of length n
            res.add(curr);
            return;
        }
        for (char ch : new char[] {'a', 'b', 'c'}) {  // Try each character
            if (curr.isEmpty() || curr.charAt(curr.length() - 1) != ch) {  // Ensure no consecutive identical chars
                backtrack(curr + ch, n, ans);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        def backtrack(curr: str, res: List[str]) -> None:
            if len(curr) == n:  # Base case: Valid happy string of length n
                res.append(curr)
                return
            for c in 'abc':  # Try each character
                if not curr or curr[-1] != c:  # Ensure no consecutive identical chars
                    backtrack(curr + c, res)

        res = []
        backtrack("", res)
        return res[k - 1] if k <= len(res) else ""  # Return kth or empty string

Complexity

• ⏰ Time complexity: O(2^n)
  • Generating all happy strings of length n involves O(2^n) operations as, for each position, we have at most 2 valid choices (excluding the previous character).
  • Accessing the kth string from the stored list is O(1), so the overall time complexity is O(2^n).
• 🧺 Space complexity: O(2^n)
  • Storing all happy strings requires O(2^n) space.
  • The recursive call stack takes O(n) space.
  • Hence, the overall space complexity is O(2^n).

Dry Runs

n = 3, k = 4

For n = 3, k = 4:

1. Generate All Happy Strings of Length 3:
   • Backtracking generates: ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] (lexicographical order).
2. Access the 4th string: "acb".

graph TD
    S["Start (Empty String)"] --> |a| A["a"]
    S --> |b| B["b"]
    S --> |c| C["c"]
    
    A --> |b| AA["ab"]
    A --> |c| AB["ac"]
    
    B --> |a| BA["ba"]
    B --> |c| BB["bc"]
    
    C --> |a| CA["ca"]
    C --> |b| CB["cb"]
    
    AA --> |a| AAA["aba"]
    AA --> |c| AAB["abc"]
    
    AB --> |a| ABA["aca"]
    AB --> |b| ABB["acb"]
    
    BA --> |b| BAA["bab"]
    BA --> |c| BAB["bac"]
    
    BB --> |a| BBA["bca"]
    BB --> |b| BBB["bcb"]
    
    CA --> |b| CAA["cab"]
    CA --> |c| CAB["cac"]
    
    CB --> |a| CBA["cba"]
    CB --> |c| CBB["cbc"]
  

n = 2, k = 8

For n = 2, k = 8 (when k exceeds count):

1. Generated Happy Strings: ["ab", "ac", "ba", "bc", "ca", "cb"].
2. Since k = 8 exceeds the count, return an empty string.

Method 2 - Using Maths

If you observe, the recursion tree is very symmetric.

Instead of generating all the happy strings explicitly (which results in exponential time complexity), we can use the ordered and structured nature of the happy strings to directly compute the kth happy string without generating all the others.

Symmetry observation

• For a given n, the strings branch at every position (a, b, c), resulting in a tree structure.
• Each valid branch creates half (2/3) of the total possibilities at each step due to the restriction (no consecutive characters are the same).
• For example, at every level:
  • If the previous character is 'a', the valid choices are 'b' and 'c'.
  • If the previous character is 'b', the valid choices are 'a' and 'c'.
  • This reduces the problem to selecting a character based on the k value and recursively narrowing down.

Mathematical Optimisation

• The total number of happy strings of length n is 3 * 2^(n-1) (derived from 3 choices for the first character and 2 choices thereafter).
• If we know the k value, we can choose the next character at each level based on which region k falls into without generating all possibilities.

Algorithm

• Start with an empty result string.
• Compute the total number of happy strings of length n (let it be total).
• For each position in the string (from 0 to n-1):
  • Divide the space of possibilities equally among valid branches (depending on the previous character).
  • Narrow down to the correct branch based on k.
  • Append the corresponding character to the result.
  • Update k to represent the relative position within the current branch.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public String getHappyString(int n, int k) {
        int total = 3 * (1 << (n - 1));  // Total happy strings of length n
        if (k > total) {
            return "";  // k exceeds the number of valid strings
        }
        
        StringBuilder ans = new StringBuilder();
        char prev = '\0';  // Tracks the previous character
        char[] chars = {'a', 'b', 'c'};
        
        for (int i = 0; i < n; i++) {
            int groupSize = 1 << (n - i - 1);  // Size of each group at this level
            for (char ch : chars) {
                if (ch != prev) {  // Valid choice (no consecutive identical letters)
                    if (k <= groupSize) {
                        ans.append(ch);
                        prev = ch;  // Update previous character
                        break;
                    }
                    k -= groupSize;  // Move to the next group
                }
            }
        }
        
        return ans.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        total = 3 * (2 ** (n - 1))  # Total happy strings of length n
        if k > total:
            return ""  # k exceeds the number of valid strings
        
        res = []
        chars = ['a', 'b', 'c']
        prev = None  # Tracks the previous character
        
        for i in range(n):
            group_size = 2 ** (n - i - 1)  # Size of each group at this level
            for c in chars:
                if c != prev:  # Valid choice (no consecutive identical letters)
                    if k <= group_size:
                        res.append(c)
                        prev = c  # Update previous character
                        break
                    k -= group_size  # Move to the next group
        
        return "".join(res)

Complexity

• ⏰ Time complexity: O(n) as at each step, we compute the valid choices and reduce the problem size in constant time.
• 🧺 Space complexity: O(1)

Dry Run

Here are the steps:

Step 1:

• Total happy strings: 3 * 2^(3-1) = 12.
• First character has 3 groups (a, b, c), each with size 2^(3-1) = 4.
• k = 4 falls in the first group (a).

Step 2 (fix the first character to a):

• Within the a group (ab, ac), each second-level group has size 2^(3-2) = 2.
• k = 4 is on the second group (ac).

Step 3 (fix the first two characters to ac):

• Within the ac group (aca, acb), each group has size 2^(3-3) = 1.
• k = 4 picks the second string (acb).

Result: "acb"