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

This is the daily question of leetcode in 2025-02-19. {: .prompt-info }

Problem Description

#

Given two integer 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 empty string if there are less than k happy strings of length n.

A happy string is a string s that:

• consists only of letters of the set ['a', 'b', 'c']
• s[i] != s[i+1] for all i

Solution - Backtracking

#

Intuition

#

• We can use backtracking to generate all the happy strings and pick the kth one.

Code

#

class Solution {
public:
    // DFS to find all happy strings
    void dfs(int n, string current, vector<string>& result){
        // If the length of the current string equals n, append it to the result
        if(current.length() == n){
            result.push_back(current);
            return;
        }
        for(char i = 'a'; i <= 'c'; i++){
            // Ensure adjacent characters are different
            if (!current.empty() && i == current.back()) continue;
            dfs(n, current + i, result);
        }
        return;
    }
    string getHappyString(int n, int k) {
        vector<string> result;
        string current = "";
        dfs(n, current, result);
        return (result.size() >= k) ? result[k-1] : "";
    }
};

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

  Since there are $3\times 2^{(n-1)}$ valid happy strings, we make $O(3\times 2^{(n-1)})$ times of recursion calls (We will explain it in below). Each recursion call takes $O(1)$ if no reallocation occurs. So, $O(3\times 2^{(n-1)}) = O(2^n)$ in total.

• Space complexity: $O(2^n)$

  We create a vector to store all of valid happy strings of length $n$, which costs $O(2^n)$. On the other hand, the recursion depth can grow up to $n$, this adds another $O(n)$ in space. Thus, the total space complexity is $O(n+2^n)= O(2^n)$.

Solution - Combinatorics

#

Intuition

#

Instead of generating all happy strings, we can directly compute the kth happy string using mathematical properties:

1. Group Structure

   • For happy string of length $n$, we categorize them into three groups based on their starting character: those beginning with a, b, and c.
   • After determining the first character, each subsequent character in the happy string has two valid choices. Thus, there are $3\times 2^{n-1}$ valid happy strings of length $n$.
   • If happy strings are indexed in a 0-based manner, we observe the following ranges:
     • Strings indexed from $0$ to $2^{n-1}-1$ start with a.
     • Strings indexed from $2^{n-1}$ to $2\times 2^{n-1}-1$ start with b.
     • Strings indexed from $2\times 2^{n-1}$ to $3\times 2^{n-1}-1$ start with c.

2. Finding the First Character

   • The quotient $q$ of

     $(k−1)\div 2^{n−1}$ determines which group the kth string belongs to:

     • $q=0 \Rightarrow$ First character is 'a'
     • $q=1 \Rightarrow$ First character is 'b'
     • $q=2 \Rightarrow$ First character is 'c'

3. Binary Representation for Subsequent Characters

   • The remainder $r$ determines its position within the selected group.

   • Since each character (except the first) has exactly two choices, we can represent the sequence using a binary encoding of $r$:

     • $r$ is converted into a binary string of length $n−1$.
     • Each bit in $r$ decides whether to pick the first or second valid choice.

Key Property: Order-Preserving Mapping

#

• The binary encoding establishes a one-to-one mapping between $r$ and the sequence of character choices, ensuring that each remainder uniquely determines a valid happy string.

The crucial step in constructing the string is:

result[index] = (bits[i]) ? options[prev][1] : options[prev][0];

• $r$ can be interpreted as a binary representation of the sequence of choices, where each bit determines whether to take the smaller or larger lexicographical option at each step.
• If bits[i] == 0, choose options[prev][0] (lexicographically smaller choice).
• If bits[i] == 1, choose options[prev][1] (lexicographically larger choice).

Each bit of r translates directly into a choice between two available characters, which ensures the order is maintained.

Code

#

class Solution {
public:
    string getHappyString(int n, int k) {
        // Compute the total number of happy strings of length n: 3 * 2^(n-1)
        int total = 3 * (1 << (n - 1));

        // If k exceeds the total count, return an empty string
        if (k > total) return "";

        // Compute the quotient (q) and remainder (r):
        // q determines which group the k-th happy string belongs to ('a', 'b', or 'c').
        // r determines its index within that group.
        auto [q, r] = div(k - 1, 1 << (n - 1));

        // Initialize the result string
        string result(n, ' ');

        // Set the first character based on q ('a' for 0, 'b' for 1, 'c' for 2)
        result[0] = 'a' + q;

        // Define possible choices for the next character based on the previous one
        {% raw %}array<array<char, 2>, 3> options = {{
            {'b', 'c'}, // If the previous character is 'a', next can be 'b' or 'c'
            {'a', 'c'}, // If the previous character is 'b', next can be 'a' or 'c'
            {'a', 'b'}  // If the previous character is 'c', next can be 'a' or 'b'
        }};{% endraw %}

        // Convert r into a binary representation since it determines the sequence of choices
        bitset<10> bits(r);

        // Iterate from i = n-2 because r has n-1 bits (excluding the first character)
        for (int i = n - 2, index = 1; i >= 0; i--, index++) {
            // Determine the previous character index (0 for 'a', 1 for 'b', 2 for 'c')
            int prev = result[index - 1] - 'a';

            // Select the next character based on the binary representation of r:
            // If bits[i] is 0, pick options[prev][0]
            // If bits[i] is 1, pick options[prev][1]
            result[index] = (bits[i]) ? options[prev][1] : options[prev][0];
        }

        return result;
    }
};

Time complexity: $O(n)$

Space complexity: $O(1)$ excluding output string

Comparison of Approaches

#

Thank you for reading! Let me know your thoughts and feedback! {: .prompt-tip }