⚡Flashcard Drill➔
NeetCode #501LC-1415MediumBacktracking
← Back to All Problems

#501 · #1415 · The k-th Lexicographical String of All Happy Strings of Length n(长度为 n 的开心字符串中字典序第 k 小的字符串)

📌 Problem Statement & Constraints

A happy string consists only of a, b, c and has no two adjacent characters equal. Given n and k, return the k-th lexicographically smallest happy string of length n, or the empty string if fewer than k exist. Constraints: 1 <= n <= 10, 1 <= k <= 100.

💡 Core Algorithmic Approaches

  1. Enumerate happy strings with a DFS that tries a, b, c in order and skips the previous character.
  2. Because the characters are tried in alphabetical order, the DFS emits the strings in lexicographic order.
  3. So the k-th emitted string is the answer; no sorting is needed.
  4. There are 3 * 2^(n-1) happy strings, so the enumeration is tiny for n <= 10.

💻 Benchmark Python3 Implementation

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

        def dfs(path: str) -> None:
            if len(path) == n:
                res.append(path)           # in lexicographic order by construction
                return
            for ch in "abc":
                if not path or path[-1] != ch:   # no two adjacent equal
                    dfs(path + ch)

        dfs("")
        return res[k - 1] if k <= len(res) else ""   # empty string when out of range

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(3 * 2^(n-1) * n): the number of happy strings times the construction cost.
💾 Space Complexity
O(n) for the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Trying the characters in a non-alphabetical order: the output would not be lexicographic, and sorting would then be needed.
  • Checking ch not in path: only the previous character matters, so a character may recur non-adjacently.
  • Returning None when k is out of range: the contract requires the empty string.
  • Generating all 3^n strings and filtering: three times the work plus a sort.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems