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

Intuition

The happy string is made from a,b,c with no two consecutive same characters. Generate them in lexicographic order and return the k-th one.

Algorithm

1BFS/DFS generating happy strings in lex order. Count k-th.
2Or: compute directly - at each position, count how many strings of remaining length start with each valid character.

Common Pitfalls

•Each position has at most 2 choices (any of a,b,c except last character). Total strings of length n = 3 * 2^(n-1).

1415.cs

// Approach: BFS generates all happy strings in lexicographic order; return the k-th if it exists.
// Time: O(3 · 2^(n-1)) Space: O(3 · 2^(n-1))

public class Solution
{
    public string GetHappyString(int n, int k)
    {
        var nextLetters = new Dictionary<char, string> {
            {'a', "bc"}, {'b', "ac"}, {'c', "ab"}
        };
        var q = new Queue<string>(new[] { "a", "b", "c" });

        while (q.Peek().Length != n)
        {
            var u = q.Dequeue();
            foreach (var nextLetter in nextLetters[u[u.Length - 1]])
                q.Enqueue(u + nextLetter);
        }

        if (q.Count < k)
            return "";

        for (int i = 0; i < k - 1; ++i)
            q.Dequeue();
        return q.Peek();
    }
}

Was this solution helpful?