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
- Enumerate happy strings with a DFS that tries
a,b,cin order and skips the previous character. - Because the characters are tried in alphabetical order, the DFS emits the strings in lexicographic order.
- So the
k-th emitted string is the answer; no sorting is needed. - There are
3 * 2^(n-1)happy strings, so the enumeration is tiny forn <= 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
Nonewhenkis out of range: the contract requires the empty string. - Generating all
3^nstrings 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.