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

Med

#1309Time: `O(N * 3 * 2^(N-1))`, where N is the length of the string. We generate `3 * 2^(N-1)` strings, and each string creation/copy takes `O(N)` time.Space: `O(N * 3 * 2^(N-1))` to store all the generated happy strings. The recursion stack depth adds an additional `O(N)`.

Patterns

Backtracking

Data structures

String

Prompt

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.

Example 1:

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:

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

Example 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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating all possible happy strings of length n using recursion (backtracking). We store these strings in a list. Since the backtracking process explores characters in lexicographical order ('a', 'b', 'c'), the resulting list will also be sorted lexicographically. Finally, we check if the list has at least k strings and return the k-th one if it exists.

Algorithm

1. Initialize an empty list happyStrings to store the results.
1. Create a recursive helper function generate(n, current, list).
1. In generate, if current.length() == n, add current.toString() to list and return.
1. In generate, loop through characters 'a', 'b', 'c'.
1. If the character can be appended (i.e., not same as the last character of current), append it, recurse, and then backtrack by removing it.
1. Call the generate function with an initial empty string builder.
1. After the function returns, check if k is within the bounds of happyStrings.size().
1. If k <= happyStrings.size(), return happyStrings.get(k - 1). Otherwise, return "".

Walkthrough

We define a recursive function, say generate(currentString, n, list). The base case for the recursion is when the currentString reaches the desired length n. At this point, we add the generated string to our list of results. In the recursive step, we iterate through the characters 'a', 'b', 'c'. For each character, we check if it's different from the last character of the currentString. If it is (or if the string is empty), we append the character and make a recursive call. After the call returns, we backtrack by removing the character we just added. The initial calls to the function will be with an empty string, which then branches out for 'a', 'b', and 'c' as the first character. After the entire generation process is complete, we have a list of all happy strings, sorted. We then simply retrieve the element at index k-1. If k is larger than the number of strings found, we return an empty string.

1class Solution {2    public String getHappyString(int n, int k) {3        List<String> happyStrings = new ArrayList<>();4        generate(n, new StringBuilder(), happyStrings);5        6        if (k > happyStrings.size()) {7            return "";8        }9        return happyStrings.get(k - 1);10    }11 12    private void generate(int n, StringBuilder current, List<String> list) {13        if (current.length() == n) {14            list.add(current.toString());15            return;16        }17 18        for (char c : new char[]{'a', 'b', 'c'}) {19            if (current.length() == 0 || current.charAt(current.length() - 1) != c) {20                current.append(c);21                generate(n, current, list);22                current.deleteCharAt(current.length() - 1); // backtrack23            }24        }25    }26}

Complexity

Time

`O(N * 3 * 2^(N-1))`, where N is the length of the string. We generate `3 * 2^(N-1)` strings, and each string creation/copy takes `O(N)` time.

Space

`O(N * 3 * 2^(N-1))` to store all the generated happy strings. The recursion stack depth adds an additional `O(N)`.

Trade-offs

Pros

Simple to understand and implement.
Correctly finds the k-th string by leveraging the natural lexicographical order of backtracking.

Cons

Highly inefficient as it generates all possible happy strings, regardless of the value of k.
Consumes a large amount of memory to store all the generated strings.

This approach is an optimization of the brute-force backtracking. Instead of generating all happy strings, we can stop the process as soon as we have found the k-th string. We use a counter to keep track of how many strings we have generated. Since the strings are generated in lexicographical order, the k-th string we encounter is the one we are looking for.

Algorithm

1. Initialize a counter count = k and an empty result string result.
1. Create a recursive helper function generate(n, current).
1. Add a pruning condition: if count <= 0, return immediately.
1. In generate, if current.length() == n, decrement count. If count becomes 0, set result = current.toString() and return.
1. In generate, loop through characters 'a', 'b', 'c'.
1. If a character can be appended, append it, recurse, and then backtrack.
1. Call the generate function with an initial empty string builder.
1. After the function returns, result will either hold the k-th string or be empty. Return result.

Walkthrough

We use a counter, initialized to k. We decrement this counter every time we find a complete happy string of length n. The backtracking logic is the same as the brute-force approach. We build the string character by character recursively. The base case is when a string of length n is formed. We decrement our counter. If the counter becomes zero, it means we have found the k-th string. We store this string in a result variable and can then prune the search space by immediately returning from all recursive calls. If the backtracking process completes and the k-th string was not found (i.e., the counter never reached zero because there are fewer than k happy strings), we return an empty string.

1class Solution {2    private int count;3    private String result = "";4 5    public String getHappyString(int n, int k) {6        this.count = k;7        generate(n, new StringBuilder());8        return result;9    }10 11    private void generate(int n, StringBuilder sb) {12        if (count <= 0) { // Pruning: if we've found the k-th or passed it13            return;14        }15 16        if (sb.length() == n) {17            count--;18            if (count == 0) {19                result = sb.toString();20            }21            return;22        }23 24        for (char c : new char[]{'a', 'b', 'c'}) {25            if (sb.length() == 0 || sb.charAt(sb.length() - 1) != c) {26                sb.append(c);27                generate(n, sb);28                sb.deleteCharAt(sb.length() - 1); // backtrack29            }30        }31    }32}

Complexity

Time

`O(k * N)`. In the worst case, we generate `k` strings of length `N`.

Space

`O(N)` for the recursion stack and the `StringBuilder`.

Trade-offs

Pros

Much more efficient than the brute-force approach, especially for small k.
Avoids storing all strings, leading to significantly better space complexity.

Cons

Still relies on recursion and explores paths one by one, which is slower than a direct mathematical calculation.

This is the most efficient approach. It leverages the predictable, tree-like structure of the lexicographically sorted happy strings. We can directly calculate which character should be at each position of the k-th string without generating any other strings.

Algorithm

1. Calculate the number of happy strings of length n-1 starting from a specific character: branch_count = 2^(n-1).
1. Check if k is greater than the total number of happy strings (3 * branch_count). If so, return "".
1. Convert k to be 0-indexed by decrementing it.
1. Determine the first character: char_index = k / branch_count. The character is 'a' + char_index. Append it to the result.
1. Update k = k % branch_count.
1. Loop from i = 1 to n-1 to determine the subsequent characters.
1. In each iteration, update branch_count by dividing it by 2.
1. Determine the index for the next character: char_index = k / branch_count.
1. Based on the previous character and char_index, find the next character from the two valid options. Append it.
1. Update k = k % branch_count.
1. Return the constructed string.

Walkthrough

The core idea is that for a string of length n, the first character determines a block of 2^(n-1) strings. The second character determines a sub-block of 2^(n-2) strings, and so on. First, we check if k is valid. The total number of happy strings of length n is 3 * 2^(n-1). If k exceeds this, we return an empty string. We convert k to be 0-indexed (k = k - 1) for easier calculations. We build the string from left to right (position i from 0 to n-1). For the first character (i=0), there are 3 choices. The number of strings in each branch is branch_count = 2^(n-1). The index of the first character is k / branch_count. We append this character and update k to be the remainder: k = k % branch_count. For each subsequent character (i > 0), there are only 2 choices. The number of strings in each sub-branch is branch_count = 2^(n-1-i). The index of the next character (among the two valid choices) is k / branch_count. We find the correct character, append it, and update k with the remainder. We repeat this process for all n positions to construct the final string.

1class Solution {2    public String getHappyString(int n, int k) {3        int totalStrings = 3 * (1 << (n - 1));4        if (k > totalStrings) {5            return "";6        }7 8        StringBuilder sb = new StringBuilder();9        k--; // Convert to 0-indexed10 11        // First character12        int branchCount = 1 << (n - 1);13        int charIndex = k / branchCount;14        char firstChar = (char) ('a' + charIndex);15        sb.append(firstChar);16        k %= branchCount;17 18        // Subsequent characters19        for (int i = 1; i < n; i++) {20            branchCount >>= 1; // branchCount = 1 << (n - 1 - i)21            char prevChar = sb.charAt(sb.length() - 1);22            charIndex = k / branchCount;23            24            char nextChar = ' ';25            if (prevChar == 'a') {26                nextChar = (charIndex == 0) ? 'b' : 'c';27            } else if (prevChar == 'b') {28                nextChar = (charIndex == 0) ? 'a' : 'c';29            } else { // prevChar == 'c'30                nextChar = (charIndex == 0) ? 'a' : 'b';31            }32            sb.append(nextChar);33            k %= branchCount;34        }35 36        return sb.toString();37    }38}

Complexity

Time

`O(N)`. The loop runs `N` times, and each step involves constant time arithmetic operations.

Space

`O(N)` to store the `StringBuilder` for the result. If we consider the output string as part of the required space, this is optimal.

Trade-offs

Pros

Extremely efficient, with linear time complexity.
Minimal space complexity, as it doesn't use recursion or store extra data structures that scale with input size beyond the result itself.
Directly computes the result without any unnecessary exploration.

Cons

The logic is more complex and less intuitive than backtracking.

Solutions

Solution

1public class Solution { public string GetHappyString ( int n , int k ) { List < string > ans = new List < string >(); StringBuilder s = new StringBuilder (); void Dfs () { if ( s . Length == n ) { ans . Add ( s . ToString ()); return ; } if ( ans . Count >= k ) { return ; } foreach ( char c in "abc" ) { if ( s . Length == 0 || s [ s . Length - 1 ] != c ) { s . Append ( c ); Dfs (); s . Length --; } } } Dfs (); return ans . Count < k ? "" : ans [ k - 1 ]; } }

1class Solution { private List < String > ans = new ArrayList <>(); public String getHappyString ( int n , int k ) { dfs ( "" , n ); return ans . size () < k ? "" : ans . get ( k - 1 ); } private void dfs ( String t , int n ) { if ( t . length () == n ) { ans . add ( t ); return ; } for ( char c : "abc" . toCharArray ()) { if ( t . length () > 0 && t . charAt ( t . length () - 1 ) == c ) { continue ; } dfs ( t + c , n ); } } }

1function getHappyString ( n , k ) { const ans = []; const dfs = ( s = '' ) => { if ( s . length === n ) { ans . push ( s ); return ; } for ( const ch of ' abc ' ) { if ( s . at ( - 1 ) === ch ) continue ; dfs ( s + ch ); } }; dfs (); return ans [ k - 1 ] ?? '' ; }

1class Solution : def getHappyString ( self , n : int , k : int ) -> str : def dfs ( t ): if len ( t ) == n : ans . append ( t ) return for c in 'abc' : if t and t [ - 1 ] == c : continue dfs ( t + c ) ans = [] dfs ( '' ) return '' if len ( ans ) < k else ans [ k - 1 ]

1class Solution { public: vector < string > ans ; string getHappyString ( int n , int k ) { dfs ( "" , n ); return ans . size () < k ? "" : ans [ k - 1 ]; } void dfs ( string t , int n ) { if ( t . size () == n ) { ans . push_back ( t ); return ; } for ( int c = 'a' ; c <= 'c' ; ++ c ) { if ( t . size () && t . back () == c ) continue ; t . push_back ( c ); dfs ( t , n ); t . pop_back (); } } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Solution { public string GetHappyString ( int n , int k ) { List < string > ans = new List < string >(); StringBuilder s = new StringBuilder (); void Dfs () { if ( s . Length == n ) { ans . Add ( s . ToString ()); return ; } if ( ans . Count >= k ) { return ; } foreach ( char c in "abc" ) { if ( s . Length == 0 || s [ s . Length - 1 ] != c ) { s . Append ( c ); Dfs (); s . Length --; } } } Dfs (); return ans . Count < k ? "" : ans [ k - 1 ]; } }

1class Solution { private List < String > ans = new ArrayList <>(); public String getHappyString ( int n , int k ) { dfs ( "" , n ); return ans . size () < k ? "" : ans . get ( k - 1 ); } private void dfs ( String t , int n ) { if ( t . length () == n ) { ans . add ( t ); return ; } for ( char c : "abc" . toCharArray ()) { if ( t . length () > 0 && t . charAt ( t . length () - 1 ) == c ) { continue ; } dfs ( t + c , n ); } } }

1function getHappyString ( n , k ) { const ans = []; const dfs = ( s = '' ) => { if ( s . length === n ) { ans . push ( s ); return ; } for ( const ch of ' abc ' ) { if ( s . at ( - 1 ) === ch ) continue ; dfs ( s + ch ); } }; dfs (); return ans [ k - 1 ] ?? '' ; }

1class Solution : def getHappyString ( self , n : int , k : int ) -> str : def dfs ( t ): if len ( t ) == n : ans . append ( t ) return for c in 'abc' : if t and t [ - 1 ] == c : continue dfs ( t + c ) ans = [] dfs ( '' ) return '' if len ( ans ) < k else ans [ k - 1 ]

1class Solution { public: vector < string > ans ; string getHappyString ( int n , int k ) { dfs ( "" , n ); return ans . size () < k ? "" : ans [ k - 1 ]; } void dfs ( string t , int n ) { if ( t . size () == n ) { ans . push_back ( t ); return ; } for ( int c = 'a' ; c <= 'c' ; ++ c ) { if ( t . size () && t . back () == c ) continue ; t . push_back ( c ); dfs ( t , n ); t . pop_back (); } } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.