Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1415 with 30 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1415 # by problem number
lcpy gen -s k_th_lexicographical_string_of_all_happy_strings_of_length_n # by problem name
['a', 'b', 'c'].s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).n and k, consider a list of all happy strings of length n sorted in lexicographical order.
Return the kth string of this list or return an empty string if there are less than k happy strings of length n.
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".
Input: n = 1, k = 4
Output: ""
Explanation: There are only 3 happy strings of length 1.
Input: n = 3, k = 9
Output: "cab"
Explanation: There are 12 different happy strings of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab".
1 <= n <= 101 <= k <= 100class Solution:
# Time: O(n)
# Space: O(n)
def get_happy_string(self, n: int, k: int) -> str:
total = 3 << (n - 1)
if k > total:
return ""
k -= 1
result: list[str] = []
for i in range(n):
block = 1 << (n - 1 - i)
prev = result[-1] if result else ""
candidates = [c for c in "abc" if c != prev]
index, k = divmod(k, block)
result.append(candidates[index])
return "".join(result)
| Time | Space |
|---|---|
| O(n) | O(n) |