MediumNo. 1405
Longest Happy String — LeetCode 1405 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, String, Heap (Priority Queue)
- Reading time
- 5 min
- Source
- leetcode.com
The problem
A string s is called happy if it satisfies the following conditions: s only contains the letters 'a', 'b', and 'c'. s does not contain any of "aaa", "bbb", or "ccc" as a substring.
Example
- Input
- a = 1, b = 1, c = 7
- Output
- "ccaccbcc"
- Explanation
- "ccbccacc" would also be a correct answer.
Python solution
class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
h = []
if a > 0:
heappush(h, [-a, 'a'])
if b > 0:
heappush(h, [-b, 'b'])
if c > 0:
heappush(h, [-c, 'c'])
ans = []
while len(h) > 0:
cur = heappop(h)
if len(ans) >= 2 and ans[-1] == cur[1] and ans[-2] == cur[1]:
if len(h) == 0:
break
nxt = heappop(h)
ans.append(nxt[1])
if -nxt[0] > 1:
nxt[0] += 1
heappush(h, nxt)
heappush(h, cur)
else:
ans.append(cur[1])
if -cur[0] > 1:
cur[0] += 1
heappush(h, cur)
return ''.join(ans)Complexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1405. Longest Happy String is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0420 | Strong Password Checker | Hard |
| 0179 | Largest Number | Medium |
| 0316 | Remove Duplicate Letters | Medium |
| 0402 | Remove K Digits | Medium |
| 0502 | IPO | Hard |
| 0630 | Course Schedule III | Hard |
Frequently asked questions
- How hard is LeetCode 1405. Longest Happy String?
LeetCode 1405. Longest Happy String is rated Medium on LeetCode.
- What topics does LeetCode 1405. Longest Happy String cover?
LeetCode 1405. Longest Happy String is tagged Greedy, String and Heap (Priority Queue) on LeetCode.