# The k-th Lexicographical String of All Happy Strings of Length n
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n)
Canonical: https://scaleengineer.com/dsa/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** String
---
## 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`.

**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
## Brute-force with Backtracking (Generate All)
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.
**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)`.
**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.
### Explanation
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.

```java
class Solution {
    public String getHappyString(int n, int k) {
        List<String> happyStrings = new ArrayList<>();
        generate(n, new StringBuilder(), happyStrings);
        
        if (k > happyStrings.size()) {
            return "";
        }
        return happyStrings.get(k - 1);
    }

    private void generate(int n, StringBuilder current, List<String> list) {
        if (current.length() == n) {
            list.add(current.toString());
            return;
        }

        for (char c : new char[]{'a', 'b', 'c'}) {
            if (current.length() == 0 || current.charAt(current.length() - 1) != c) {
                current.append(c);
                generate(n, current, list);
                current.deleteCharAt(current.length() - 1); // backtrack
            }
        }
    }
}
```
### Algorithm
- 1. Initialize an empty list `happyStrings` to store the results.
- 2. Create a recursive helper function `generate(n, current, list)`.
- 3. In `generate`, if `current.length() == n`, add `current.toString()` to `list` and return.
- 4. In `generate`, loop through characters 'a', 'b', 'c'.
- 5. 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.
- 6. Call the `generate` function with an initial empty string builder.
- 7. After the function returns, check if `k` is within the bounds of `happyStrings.size()`.
- 8. If `k <= happyStrings.size()`, return `happyStrings.get(k - 1)`. Otherwise, return `""`.

## Optimized Backtracking with Early Exit
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.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    private int count;
    private String result = "";

    public String getHappyString(int n, int k) {
        this.count = k;
        generate(n, new StringBuilder());
        return result;
    }

    private void generate(int n, StringBuilder sb) {
        if (count <= 0) { // Pruning: if we've found the k-th or passed it
            return;
        }

        if (sb.length() == n) {
            count--;
            if (count == 0) {
                result = sb.toString();
            }
            return;
        }

        for (char c : new char[]{'a', 'b', 'c'}) {
            if (sb.length() == 0 || sb.charAt(sb.length() - 1) != c) {
                sb.append(c);
                generate(n, sb);
                sb.deleteCharAt(sb.length() - 1); // backtrack
            }
        }
    }
}
```
### Algorithm
- 1. Initialize a counter `count = k` and an empty result string `result`.
- 2. Create a recursive helper function `generate(n, current)`.
- 3. Add a pruning condition: if `count <= 0`, return immediately.
- 4. In `generate`, if `current.length() == n`, decrement `count`. If `count` becomes 0, set `result = current.toString()` and return.
- 5. In `generate`, loop through characters 'a', 'b', 'c'.
- 6. If a character can be appended, append it, recurse, and then backtrack.
- 7. Call the `generate` function with an initial empty string builder.
- 8. After the function returns, `result` will either hold the k-th string or be empty. Return `result`.

## Direct Construction using Mathematical Properties
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public String getHappyString(int n, int k) {
        int totalStrings = 3 * (1 << (n - 1));
        if (k > totalStrings) {
            return "";
        }

        StringBuilder sb = new StringBuilder();
        k--; // Convert to 0-indexed

        // First character
        int branchCount = 1 << (n - 1);
        int charIndex = k / branchCount;
        char firstChar = (char) ('a' + charIndex);
        sb.append(firstChar);
        k %= branchCount;

        // Subsequent characters
        for (int i = 1; i < n; i++) {
            branchCount >>= 1; // branchCount = 1 << (n - 1 - i)
            char prevChar = sb.charAt(sb.length() - 1);
            charIndex = k / branchCount;
            
            char nextChar = ' ';
            if (prevChar == 'a') {
                nextChar = (charIndex == 0) ? 'b' : 'c';
            } else if (prevChar == 'b') {
                nextChar = (charIndex == 0) ? 'a' : 'c';
            } else { // prevChar == 'c'
                nextChar = (charIndex == 0) ? 'a' : 'b';
            }
            sb.append(nextChar);
            k %= branchCount;
        }

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

# Solutions
### CSharp

```csharp
public 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 ]; } }
```

### Java

```java
class 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 ); } } }
```

### JavaScript

```javascript
function 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 ] ?? '' ; }
```

### Python

```python
class 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 ]
```

### CPP

```cpp
class 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 (); } } };
```