DDSA Solutions

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

UnknownView on LeetCode
StringBacktracking

Problem Overview

The happy string is made from a,b,c with no two consecutive same characters.

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

  1. 1BFS/DFS generating happy strings in lex order. Count k-th.
  2. 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
C#
// 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?

Related Problems