Is String Without AAA or BBB easy or hard?

LeetCode classifies the problem as Medium. The implementation is short, but the challenge is recognizing the greedy rule that balances the counts while preventing three identical characters in a row.

String Without AAA or BBB Python/Java solution

Both Python and Java implementations follow the same greedy pattern. Maintain counters for 'a' and 'b', repeatedly append the character with the larger count, and check the last two characters of the result before adding another. The loop continues until all characters are used.

How to solve String Without AAA or BBB in O(n)?

Treat n as a+b. Use a greedy rule while constructing the string: prefer the character with the larger remaining count, but check the last two characters of the result. If adding that character would form 'aaa' or 'bbb', append the other character instead. Each iteration consumes one character, resulting in linear time.

What is the best approach for String Without AAA or BBB?

The greedy alternating strategy is the most practical solution. Always append the character with the larger remaining count unless it would create three consecutive identical characters. If the last two characters are the same, force the other character. This builds the string in O(a+b) time with O(1) extra space.

Is String Without AAA or BBB asked at Google/Amazon/Meta?

Variants of constrained string construction problems appear in interviews at companies like Google, Amazon, and Meta. Interviewers use them to evaluate greedy decision making and the ability to enforce constraints while building sequences.

What data structure is used in String Without AAA or BBB?

The solution mainly uses a mutable string builder or array buffer to append characters efficiently. Only two counters track the remaining 'a' and 'b' characters, and a quick check of the last two characters prevents invalid triples.

What is the time complexity of String Without AAA or BBB?

The optimal algorithms run in O(a+b) time because each step appends exactly one character and the final string length is a+b. Space complexity is O(1) excluding the output string since only counters and a few checks on the last characters are required.

Description Solution Video 4:25

984. String Without AAA or BBB

Medium45.6% acceptance3 companies

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 1:

Input: a = 1, b = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.

Example 2:

Input: a = 4, b = 1
Output: "aabaa"

Constraints:

0 <= a, b <= 100
It is guaranteed such an s exists for the given a and b.

Asked at 3 companies

Zalando

Google Amazon

Topics

Greedy String

4:25

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def strWithout3a3b(self, a: int, b: int) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

1
2

Input

4
1

Your code is saved on this device.Solution