MediumNo. 1415
The k-th Lexicographical String of All Happy Strings of Length n — LeetCode 1415 Python Solution
- Pattern
- Backtracking
- Topics
- String, Backtracking
- Reading time
- 3 min
- Source
- leetcode.com
The problem
A happy string is a string that: consists only of letters of the set ['a', 'b', 'c']. s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).
Example
- Input
- n = 1, k = 3
- Output
- "c"
- Explanation
- The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c".
Python solution
class Solution:
def getHappyString(self, n: int, k: int) -> str:
def dfs():
if len(s) == n:
ans.append("".join(s))
return
if len(ans) >= k:
return
for c in "abc":
if not s or s[-1] != c:
s.append(c)
dfs()
s.pop()
ans = []
s = []
dfs()
return "" if len(ans) < k else ans[k - 1]Complexity
- Time
- O(n × 2n)
- Space · auxiliary
- O(n)
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0079 | Word Search | Medium |
| 0093 | Restore IP Addresses | Medium |
| 0212 | Word Search II | Hard |
| 0257 | Binary Tree Paths | Easy |
| 0282 | Expression Add Operators | Hard |
| 0301 | Remove Invalid Parentheses | Hard |
Frequently asked questions
- How hard is LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n?
LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n?
The Python solution on this page runs in O(n × 2n).
- What is the space complexity of LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n cover?
LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n is tagged String and Backtracking on LeetCode.