Problem Informations

• Problem Index: 1415
• Problem Link: The k-th Lexicographical String of All Happy Strings of Length n
• Topics: String, Backtracking

Problem Description

A happy string is a string that:

• consists only of letters of the set $[‘a’, ‘b’, ‘c’]$.
• $s[i] \neq 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 \leq n \leq 10$
• $1 \leq k \leq 100$

Intuition

This problem can actually be solved by simulating a ternary number system. Since we can only use the characters ‘a’, ‘b’, and ‘c’, and adjacent characters cannot be the same, we are essentially generating a special ternary sequence. We can treat ‘a’, ‘b’, and ‘c’ as 0, 1, and 2, and generate all possible happy strings through a carry-based simulation. By using an extra leading position (i.e., an array of length n+1), we can simplify the carry operations and handle edge cases more easily.

Approach

Our solution is based on the following strategy:

1. Initialization:

   • Create an array of length n+1, initialized with all ‘a’s.
   • The first position (index 0) serves as a carry indicator and is not part of the actual string.

2. Special Case Handling:

   • When n = 1, since the initial ‘a’ is already a happy string, decrease k by 1.

3. Ternary Simulation:

   • Use the last character as the least significant digit for increment operations.
   • When a character exceeds ‘c’, reset it to ‘a’ and carry over to the next position.
   • If the carry reaches the first position (index 0) and exceeds ‘a’, it means all possible happy strings have been generated.

4. Happy String Validation:

   • Check if adjacent characters are different.
   • Only count when the entire string meets the conditions (decrease k by 1).

5. Result Retrieval:

   • Return the result when the kth valid happy string is found (k = 0).
   • Return an empty string if the kth happy string cannot be found (first digit exceeds ‘a’).

Code

C++

class Solution {
public:
    string getHappyString(int n, int k) {
        // Create a vector of size n+1 initialized with 'a' to store the current happy string.
        vector<char> currentString(n + 1, 'a');
        
        // When n == 1, there are only three possible happy strings: "a", "b", "c".
        // We decrement k by 1 to match the 0-based index.
        if (n == 1) k--;

        // Loop until the kth happy string is found.
        while (k > 0) {
            // Increment the last character of the string.
            currentString[n]++;
            
            // Check from the end if any character is beyond 'c' and reset it to 'a'.
            // Increment the preceding character.
            int i;
            for (i = n; currentString[i] > 'c'; i--) {
                currentString[i] = 'a';
                currentString[i - 1]++;
            }
            
            // If the first character goes beyond 'c', there cannot be a kth happy string.
            if (currentString[0] != 'a') return "";

            // Check if the string is a happy string by ensuring no two consecutive characters are the same.
            for (i = 1; i < n; i++) {
                if (currentString[i] == currentString[i + 1]) break;
            }

            // If a valid happy string is found, decrement k.
            if (i == n) k--;
        }
        
        // Return the kth happy string by excluding the first placeholder character.
        return string(currentString.begin() + 1, currentString.end());
    }
};

Python

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        # Create a list of size n+1 initialized with 'a' to store the current happy string.
        currentString = ['a'] * (n + 1)
        
        # When n == 1, there are only three possible happy strings: "a", "b", "c".
        # We decrement k by 1 to match the 0-based index.
        if n == 1:
            k -= 1

        # Loop until the kth happy string is found.
        while k > 0:
            # Increment the last character of the string.
            currentString[n] = chr(ord(currentString[n]) + 1)
            
            # Check from the end if any character is beyond 'c' and reset it to 'a'.
            # Increment the preceding character.
            i = n
            while currentString[i] > 'c':
                currentString[i] = 'a'
                currentString[i - 1] = chr(ord(currentString[i - 1]) + 1)
                i -= 1
            
            # If the first character goes beyond 'c', there cannot be a kth happy string.
            if currentString[0] != 'a':
                return ""

            # Check if the string is a happy string by ensuring no two consecutive characters are the same.
            for i in range(1, n):
                if currentString[i] == currentString[i + 1]:
                    break

            # If a valid happy string is found, decrement k.
            if i == n:
                k -= 1
        
        # Return the kth happy string by excluding the first placeholder character.
        return ''.join(currentString[1:])

Complexity

• Time complexity: $O(3^n)$

  The algorithm generates all possible happy strings of length $n$ by considering each character from the set $[‘a’, ‘b’, ‘c’]$. In the worst case, for each of the $n$ positions in the string, there can be up to 3 choices, implying a total of $3^n$ possible strings. The loops in the algorithm do not individually contribute additional complexity in comparison to the generation of these strings. Therefore, the time complexity is governed by the exponential number of strings that need to be checked.

• Space complexity: $O(n)$

  The space complexity is primarily determined by the storage required for the vector currentString which holds the current happy string being constructed. Since this vector is of size $n+1$, it contributes a space complexity of $O(n)$. Other space requirements, such as loop variables or function call stack, do not exceed this linear space requirement.