Tejav
#1415

The k-th Lexicographical String of All Happy Strings of Length n

Medium
StringBacktracking
LeetCode ↗

Approaches

💡

Intuition

Time Space

We can generate all possible strings of length n using the characters 'a', 'b', and 'c', while ensuring that no two adjacent characters are the same. Once we have all valid strings, we can sort them and return the k-th string.

⚙️

Algorithm

3 steps
  1. 1Step 1: Use a recursive function to generate all happy strings of length n.
  2. 2Step 2: Ensure that the last character added is not the same as the new character being added.
  3. 3Step 3: Store valid strings in a list, sort the list, and return the k-th string if it exists.
solution.py19 lines
1# Full working Python code
2from typing import List
3
4def generate_happy_strings(n: int, k: int) -> str:
5    def backtrack(current: str):
6        if len(current) == n:
7            happy_strings.append(current)
8            return
9        for char in 'abc':
10            if not current or current[-1] != char:
11                backtrack(current + char)
12
13    happy_strings = []
14    backtrack('')
15    happy_strings.sort()
16    return happy_strings[k - 1] if k <= len(happy_strings) else ''
17
18# Example usage
19print(generate_happy_strings(1, 3))  # Output: 'c'

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.