LeetCode 984: String Without AAA or BBB

Problem Restatement

We are given two integers a and b.

We need to return any string s such that:

The problem guarantees that a valid answer exists.

The constraints are 0 <= a, b <= 100.

Input and Output

Function shape:

def strWithout3a3b(a: int, b: int) -> str:
    ...

Examples

Example 1:

a = 1
b = 2

Valid answers include:

"abb"
"bab"
"bba"

All have one 'a', two 'b' characters, and no "aaa" or "bbb".

Example 2:

a = 4
b = 1

One valid answer is:

"aabaa"

It has four 'a' characters and one 'b'.

It does not contain "aaa".

First Thought: Backtracking

One direct way is to build the string character by character.

At each step, try to append 'a' or 'b', as long as doing so does not create "aaa" or "bbb".

class Solution:
    def strWithout3a3b(self, a: int, b: int) -> str:
        def backtrack(a_left: int, b_left: int, path: list[str]) -> str | None:
            if a_left == 0 and b_left == 0:
                return "".join(path)

            if a_left > 0 and not (len(path) >= 2 and path[-1] == "a" and path[-2] == "a"):
                path.append("a")
                result = backtrack(a_left - 1, b_left, path)
                if result is not None:
                    return result
                path.pop()

            if b_left > 0 and not (len(path) >= 2 and path[-1] == "b" and path[-2] == "b"):
                path.append("b")
                result = backtrack(a_left, b_left - 1, path)
                if result is not None:
                    return result
                path.pop()

            return None

        return backtrack(a, b, []) or ""

This is correct, but it is more complicated than needed.

Problem With Backtracking

The problem guarantees that an answer exists.

So we do not need to search all possibilities.

We can build one valid answer greedily.

The only danger is placing the same character three times in a row. If we always avoid that, and prefer the character with more remaining copies, we keep the string balanced enough to finish.

Key Insight

At each step, choose the character with the larger remaining count.

But there is one exception.

If the last two characters are already the same, we must append the other character.

For example, if the current result ends with:

"aa"

then the next character cannot be 'a'.

It must be 'b'.

Similarly, if the current result ends with:

"bb"

then the next character must be 'a'.

This greedy rule works because it spends the more frequent character first, but never violates the no-three-in-a-row condition.

Algorithm

Maintain a list answer.

While either a or b is still positive:

1. If the last two characters are "aa", append 'b'.
2. Else if the last two characters are "bb", append 'a'.
3. Else append the character with the larger remaining count.
4. Decrease the corresponding count.

Finally, join the list into a string.

Correctness

The algorithm only appends one character at a time.

If the last two characters are "aa", the algorithm appends 'b', so it never creates "aaa".

If the last two characters are "bb", the algorithm appends 'a', so it never creates "bbb".

In all other cases, appending either character cannot create three equal consecutive characters, because the current suffix does not already contain two copies of that character. The algorithm chooses the character with the larger remaining count to reduce imbalance.

Each append decreases exactly one of a or b, so the final string contains exactly the original number of 'a' and 'b' characters.

Since the problem guarantees a valid answer exists, whenever the algorithm is forced to append the other character, that character is available. Therefore, the algorithm constructs a valid string of length a + b.

Complexity

Let n = a + b.

Implementation

class Solution:
    def strWithout3a3b(self, a: int, b: int) -> str:
        answer = []

        while a > 0 or b > 0:
            if len(answer) >= 2 and answer[-1] == answer[-2] == "a":
                answer.append("b")
                b -= 1
            elif len(answer) >= 2 and answer[-1] == answer[-2] == "b":
                answer.append("a")
                a -= 1
            elif a >= b:
                answer.append("a")
                a -= 1
            else:
                answer.append("b")
                b -= 1

        return "".join(answer)

Code Explanation

We build the result as a list:

answer = []

A list is efficient because appending is O(1).

The loop continues until all characters are used:

while a > 0 or b > 0:

If the result already ends with two 'a' characters:

if len(answer) >= 2 and answer[-1] == answer[-2] == "a":

we must append 'b':

answer.append("b")
b -= 1

If the result already ends with two 'b' characters, we must append 'a':

answer.append("a")
a -= 1

Otherwise, we choose the character with the larger remaining count:

elif a >= b:
    answer.append("a")
    a -= 1
else:
    answer.append("b")
    b -= 1

At the end, convert the list into a string:

return "".join(answer)

Testing

Because many outputs are valid, tests should check the properties instead of checking one exact string.

def is_valid(result: str, a: int, b: int) -> bool:
    return (
        len(result) == a + b
        and result.count("a") == a
        and result.count("b") == b
        and "aaa" not in result
        and "bbb" not in result
    )

def run_tests():
    s = Solution()

    result = s.strWithout3a3b(1, 2)
    assert is_valid(result, 1, 2)

    result = s.strWithout3a3b(4, 1)
    assert is_valid(result, 4, 1)

    result = s.strWithout3a3b(2, 5)
    assert is_valid(result, 2, 5)

    result = s.strWithout3a3b(0, 2)
    assert is_valid(result, 0, 2)

    result = s.strWithout3a3b(3, 3)
    assert is_valid(result, 3, 3)

    print("all tests passed")

run_tests()