Problem Description

You are given two integers, n and k. A happy string is a string that:

• Consists only of the characters 'a', 'b', and 'c'.
• No two adjacent characters are the same (i.e., the string has no repeating consecutive characters).

Key constraints:

• Each happy string must use only the allowed characters.
• No two adjacent characters can be the same.
• Return exactly one valid result, or an empty string if there are not enough happy strings.

Thought Process

At first, you might think about generating all possible strings of length n using the characters 'a', 'b', and 'c', then filtering out those with consecutive duplicates, and finally sorting them to pick the k-th one. However, this brute-force approach is inefficient, especially as n grows, since the number of possible strings increases exponentially.

The key realization is that we can generate happy strings in lexicographical order directly, without generating all possible combinations. By understanding the structure and constraints of happy strings, we can "skip" over large groups of strings that don't meet our criteria or that are not in the correct lexicographical position, allowing us to find the k-th string efficiently.

This leads to the idea of backtracking or constructive enumeration, where we build the string character by character, always choosing the smallest valid character at each step, and counting how many valid strings are possible from that point onward to guide our search.

Solution Approach

We want to efficiently find the k-th lexicographically smallest happy string of length n. Here's a step-by-step approach:

1. Understand Lexicographical Order:
   • The order is similar to dictionary order: 'a' < 'b' < 'c'.
   • We can build the string from left to right, always trying 'a' before 'b', and 'b' before 'c'.
2. Recursive Construction:
   • At each position, choose a character different from the previous one.
   • For each valid choice, recursively build the rest of the string.
3. Counting to Skip Unnecessary Branches:
   • At each step, calculate how many happy strings can be formed for the remaining positions with the current prefix.
   • If the number of strings with a certain prefix is less than k, we can skip that branch and decrement k accordingly.
   • If not, we proceed down that branch.
4. Implementation Details:
   • At each recursion, for each possible next character (not equal to the previous character), calculate the number of happy strings for the remaining length.
   • For a given position, the number of choices is always 2 (since we can't use the previous character).
   • So, for n positions, the total number of happy strings is 3 * 2^(n-1) (3 choices for the first character, 2 for each subsequent position).
5. Base Case:
   • When the string reaches length n, check if we've found the k-th string.

This approach efficiently finds the answer without generating all possible happy strings.

Example Walkthrough

Let's use n = 3 and k = 9 as an example.

1. First character:
   • Options: 'a', 'b', 'c'
   • For each first character, there are 2^{n-1} = 4 happy strings.
   • So, strings starting with 'a': positions 1-4; with 'b': 5-8; with 'c': 9-12.
   • Since k = 9, it falls into the group starting with 'c'.
2. Second character:
   • Previous character is 'c'. Possible next: 'a' or 'b'.
   • Each choice gives 2 happy strings (for the third character).
   • So, 'ca': positions 9-10; 'cb': 11-12.
   • k=9 is the first in 'ca'. So, prefix is 'ca'.
3. Third character:
   • Previous: 'a'. Choices: 'b' or 'c'.
   • Since k=9 is the first, we pick 'b'.
4. Result: The answer is "cab".

This step-by-step process shows how we can narrow down the answer without generating every string.

Time and Space Complexity

• Brute-force approach:
  • Generate all happy strings (up to 3 * 2^{n-1}), sort, and select the k-th.
  • Time Complexity: O(3 * 2^n-1 * n) (generating and checking all strings)
  • Space Complexity: O(3 * 2^n-1 * n) (storing all strings)
• Optimized approach (as described above):
  • At each position, we make at most 3 choices, but we prune branches using counting.
  • In practice, the recursion depth is n, and we only traverse one path to the answer.
  • Time Complexity: O(n) (since we build the string character by character)
  • Space Complexity: O(n) (for the recursion stack and the result string)

Code Implementation

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        chars = ['a', 'b', 'c']
        res = ""
        total = 3 * (2 ** (n-1))
        if k > total:
            return ""
        k -= 1  # zero-based index
        prev = ""
        for i in range(n):
            for c in chars:
                if c == prev:
                    continue
                cnt = 2 ** (n - i - 1)
                if k >= cnt:
                    k -= cnt
                else:
                    res += c
                    prev = c
                    break
        return res
      

class Solution {
public:
    string getHappyString(int n, int k) {
        vector<char> chars = {'a', 'b', 'c'};
        string res = "";
        int total = 3 * (1 << (n-1));
        if (k > total) return "";
        k--; // zero-based
        char prev = 0;
        for (int i = 0; i < n; ++i) {
            for (char c : chars) {
                if (c == prev) continue;
                int cnt = 1 << (n - i - 1);
                if (k >= cnt) {
                    k -= cnt;
                } else {
                    res += c;
                    prev = c;
                    break;
                }
            }
        }
        return res;
    }
};
      

class Solution {
    public String getHappyString(int n, int k) {
        char[] chars = {'a', 'b', 'c'};
        StringBuilder res = new StringBuilder();
        int total = 3 * (1 << (n-1));
        if (k > total) return "";
        k--; // zero-based
        char prev = 0;
        for (int i = 0; i < n; ++i) {
            for (char c : chars) {
                if (c == prev) continue;
                int cnt = 1 << (n - i - 1);
                if (k >= cnt) {
                    k -= cnt;
                } else {
                    res.append(c);
                    prev = c;
                    break;
                }
            }
        }
        return res.toString();
    }
}
      

var getHappyString = function(n, k) {
    const chars = ['a', 'b', 'c'];
    let res = '';
    let total = 3 * (1 << (n-1));
    if (k > total) return '';
    k--; // zero-based
    let prev = '';
    for (let i = 0; i < n; ++i) {
        for (let c of chars) {
            if (c === prev) continue;
            let cnt = 1 << (n - i - 1);
            if (k >= cnt) {
                k -= cnt;
            } else {
                res += c;
                prev = c;
                break;
            }
        }
    }
    return res;
};
      

Summary

The problem of finding the k-th lexicographical happy string of length n can be solved efficiently by leveraging combinatorics and lexicographical order. Instead of generating all possible strings, we use recursive construction and counting to "skip" over groups of strings, directly building the answer character by character. This approach is both elegant and efficient, reducing the time complexity from exponential to linear in n, and demonstrates the power of combining backtracking with combinatorial reasoning.