Problem Statement in English

You’re given two integers $n$ and $k$. A happy string is a string in which no character is the same as the previous character.

You’ve to return the $k^{th}$ lexicographically happy string of length $n$.

Approach

This is a clear backtracking problem. They’ve just given a heuristic to prune the search space. The heuristic is that the string should be lexicographically smallest. So, we can start with the smallest character and then move to the next character.

Boils down to a question on implementation.

Solution in Python


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        buffer = []
        letters = ["a", "b", "c"]

        count = 0

        def dfs():
            if len(buffer) == n:
                nonlocal count
                count += 1

                if count == k:
                    return True
                return False
            
            for l in letters:
                if buffer and buffer[-1] == l:
                    continue
                buffer.append(l)

                if dfs():
                    return True
                buffer.pop()

        dfs()

        return "".join(buffer)

Complexity

  • Time: $O(min(3 \cdot 2^{n-1}, k))$
    where $n$ is the length of the string. This is because we are generating all possible happy strings of length $n$ and stopping once we reach the $k^{th}$ one. Therefore we either generate all strings up to the $k^{th}$ one or all strings of length $n$, whichever is smaller.

    Further, since the letters are only “a”, “b”, and “c”, the number of happy strings of length $n$ is at most $3 \cdot 2^{n-1}$ (since the first character can be any of the 3 letters, and each subsequent character can be any of the 2 letters different from the previous one). Therefore, the time complexity can also be expressed as $O(min(3 \cdot 2^{n-1}, k))$.

  • Space: $O(n)$
    where $n$ is the length of the string.

And we are done.