Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A happy string can be built character by character, rejecting only a character equal to the previous one. Trying a, b, and c in that order makes depth-first generation produce complete strings in lexicographical order.

Approach

Backtrack from an empty prefix. Append each allowed character and recurse, storing the prefix when its length reaches n. After generating every happy string, return the entry at index k - 1, or an empty string if fewer than k strings exist. The reference solutions deliberately store all results rather than stopping at the requested rank, which explains their exponential storage cost.

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        res = []

        def bt(curr):
            if len(curr) == n:
                res.append(curr)
                return

            for c in 'abc':
                if not curr or curr[-1] != c:
                    bt(curr + c)

        bt('')

        if k > len(res):
            return ''
        return res[k - 1]

Complexity analysis

There are 3·2^(n-1) happy strings. Constructing them takes O(n·2^n) time, and the displayed implementations store every length-n string, so auxiliary space is O(n·2^n) plus O(n) recursion depth. Only one O(n) string is ultimately returned.