Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

A happy string uses only a, b, and c, and no two neighboring characters may be equal. The task is to consider every happy string of length n in lexicographic order and return the k-th one. If fewer than k such strings exist, the answer is the empty string.

Generating every valid string would work for the given idea, but it does unnecessary work. The key is that happy strings form predictable blocks. Once the first character is fixed, each later position has exactly two choices: either character other than the previous one.

Deriving the optimal solution

There are three choices for the first character and two choices for each of the remaining n - 1 positions. Therefore, the total number of happy strings is

$$ 3 \cdot 2^{n-1}. $$

If k is larger than that total, no answer exists.

Now build the answer from left to right. At any position, consider the legal next characters in the order a, b, c. If there are r positions left after choosing one of them, that choice begins a block containing exactly $2^r$ complete happy strings. Those strings are consecutive in lexicographic order because they share the same prefix.

For each candidate character:

  1. If k is larger than its block, skip the whole block and subtract its size from k.
  2. Otherwise, the desired string lies inside that block, so append the candidate and move to the next position.

For example, when n = 3, the strings beginning with a form a block of four: aba, abc, aca, and acb. The b block and then the c block have the same size. A request for the sixth string skips the four-string a block, changes k from 6 to 2, and continues inside the b block.

This is combinatorial unranking: it locates a ranked object without enumerating everything before it. The algorithm examines at most three candidate characters per position, so it takes $O(n)$ time. The character list uses $O(n)$ space for the returned string; aside from that output storage, the extra space is $O(1)$.

Python solution

class Solution:
    """Find a happy string by its one-indexed lexicographic rank."""

    _ALPHABET = ("a", "b", "c")

    def getHappyString(self, n: int, k: int) -> str:
        """Return the k-th happy string of length n, or an empty string."""
        if n <= 0 or k <= 0:
            return ""

        total_happy_strings = 3 * self._completion_count(n - 1)
        if k > total_happy_strings:
            return ""

        result: list[str] = []
        previous_character = ""

        for position in range(n):
            remaining_positions = n - position - 1
            block_size = self._completion_count(remaining_positions)

            # Legal candidates appear in lexicographic order. Each candidate
            # owns one equal-sized, contiguous block of completed strings.
            for candidate in self._ALPHABET:
                if candidate == previous_character:
                    continue

                if k > block_size:
                    k -= block_size
                    continue

                result.append(candidate)
                previous_character = candidate
                break

        return "".join(result)

    @staticmethod
    def _completion_count(remaining_positions: int) -> int:
        """Count valid suffixes after a nonempty happy prefix."""
        return 1 << remaining_positions

Interview follow-ups

How would a backtracking solution work?

A depth-first search can append each legal character in a, b, c order. That traversal produces complete happy strings in lexicographic order, so it can count completed strings and stop as soon as it reaches the k-th one. The approach is often the easiest first solution to explain because it mirrors the definition directly.

It is correct because every happy string corresponds to exactly one root-to-leaf path, illegal equal-adjacent choices are never explored, and lexicographic child order gives lexicographic leaf order. Its recursion stack and current path use $O(n)$ space. In the worst case it explores all $3 \cdot 2^{n-1}$ strings and spends $O(n \cdot 2^n)$ time if each completed path is copied. Stopping at k can make it practical, but block skipping gives a stronger $O(n)$ bound.

How would the method change for a larger alphabet?

With an ordered alphabet of size m, the first position has m choices and every later position has m - 1 choices. The total becomes $m(m-1)^{n-1}$, while a candidate at a position with r remaining characters owns $(m-1)^r$ completions. The same subtract-or-choose process therefore works unchanged in principle.

The proof still relies on equal-sized prefix blocks and lexicographic contiguity. Scanning all alphabet characters at every position costs $O(nm)$ time and $O(n)$ output space. For a very large alphabet, the next character can instead be selected arithmetically from the block index while adjusting around the forbidden previous character, reducing selection to $O(1)$ per position.

What if allowed next characters depend on more than the previous character?

Model the rule as states and transitions. A dynamic programming table can store how many valid suffixes of each remaining length can be produced from every state. While constructing the answer, try legal next characters in lexicographic order and use the table to measure each candidate’s block before skipping or choosing it.

This works because strings with a shared prefix remain contiguous even when block sizes differ; dynamic programming supplies the correct size of each block. With s states, e allowed transitions, and length n, preprocessing typically costs $O(ne)$ time and $O(ns)$ space. Rolling rows reduce count storage when only the total is needed, but unranking usually benefits from retaining counts for every remaining length.

How would you find the rank of a given happy string?

Process the string from left to right. Before accepting its actual character at a position, add the block size for every smaller legal candidate that could have appeared there. Then continue with the actual character as the new prefix. Add one at the end because ranks are one-indexed.

Every earlier string first differs at exactly one position where it uses a smaller legal character, so the accumulated blocks count each earlier string once and only once. With the fixed three-character alphabet, ranking takes $O(n)$ time and $O(1)$ extra space. The method should reject any string containing a character outside the alphabet or equal adjacent characters.

What changes if n is enormous but k is comparatively small?

The logical algorithm remains the same, but computing exact powers can create integers with far more bits than the decision needs. Each count can be capped at k: any block known to contain at least k strings is already large enough to prove that the target lies inside it, so its exact size is irrelevant.

Capping preserves every comparison and subtraction that can affect the selected rank while avoiding oversized counts. The construction still needs $O(n)$ time to emit an n-character answer and $O(n)$ output space, but its arithmetic stays bounded by the bit length of k rather than growing with the total number of happy strings.