MediumNo. 0984
String Without AAA or BBB — LeetCode 984 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, String
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given two integers a and b, return any string s such that: s has length a + b and contains exactly a 'a' letters, and exactly b 'b' letters, The substring 'aaa' does not occur in s, and The substring 'bbb' does not occur in s.
Example
- Input
- a = 1, b = 2
- Output
- "abb"
- Explanation
- "abb", "bab" and "bba" are all correct answers.
Python solution
class Solution:
def strWithout3a3b(self, a: int, b: int) -> str:
ans = []
while a and b:
if a > b:
ans.append('aab')
a, b = a - 2, b - 1
elif a < b:
ans.append('bba')
a, b = a - 1, b - 2
else:
ans.append('ab')
a, b = a - 1, b - 1
if a:
ans.append('a' * a)
if b:
ans.append('b' * b)
return ''.join(ans)Complexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 984. String Without AAA or BBB is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0179 | Largest Number | Medium |
| 0316 | Remove Duplicate Letters | Medium |
| 0402 | Remove K Digits | Medium |
| 0420 | Strong Password Checker | Hard |
| 0649 | Dota2 Senate | Medium |
| 0680 | Valid Palindrome II | Easy |
Frequently asked questions
- How hard is LeetCode 984. String Without AAA or BBB?
LeetCode 984. String Without AAA or BBB is rated Medium on LeetCode.
- What topics does LeetCode 984. String Without AAA or BBB cover?
LeetCode 984. String Without AAA or BBB is tagged Greedy and String on LeetCode.