String Without AAA or BBB: Greedy Interleaving

Given two integers a and b, build a string of length a + b that contains exactly a copies of 'a' and b copies of 'b', with no occurrence of "aaa" or "bbb" as a substring. Any valid string is accepted.

This is LeetCode 984: String Without AAA or BBB, a medium problem that tests your ability to apply greedy interleaving. The trick is to always prioritize the character you have more of, placing two at a time when safe, and switching to the other character before a triple violation occurs.

Why this problem matters

String Without AAA or BBB is a clean example of the "greedy character scheduling" pattern. You have a limited supply of two resources and a constraint on how many consecutive uses are allowed. The challenge is distributing them so no resource appears three times in a row.

This same pattern appears in problems like task scheduling with cooldowns, reorganizing strings so no two adjacent characters match, and interleaving sequences to satisfy ordering constraints. Once you learn to think in terms of "which character has more left, and how many can I safely place," you can apply the same logic to a whole family of problems.

The problem also reinforces an important greedy principle: when one resource is more abundant, use it more aggressively. If you spread both characters evenly, you risk running out of the less frequent one too early, which forces consecutive repetitions of the other.

The brute force approach

A brute force strategy would generate all permutations of a copies of 'a' and b copies of 'b', then check each permutation for "aaa" or "bbb". Return the first valid one.

from itertools import permutations

def str_without3a3b_brute(a, b):
    chars = ['a'] * a + ['b'] * b
    for perm in set(permutations(chars)):
        s = ''.join(perm)
        if 'aaa' not in s and 'bbb' not in s:
            return s
    return ""

This is wildly impractical. The number of permutations is (a + b)! / (a! * b!), which grows exponentially. For a = 50 and b = 50, you would need to check billions of strings. The greedy approach builds the answer in a single pass with O(a + b) time.

The key insight: always favor the majority character

At each step, look at how many a's and b's remain. Whichever character has more remaining should be placed next, because it is the one most at risk of being forced into three consecutive copies later. If the majority character already occupies the last two positions of the result, switch to the minority character for one step to break the streak.

When the majority count is strictly greater than the minority count, place two of the majority character. This uses up the surplus faster and reduces the risk of a forced triple later. When the counts are equal or the majority was just placed twice, place just one of the minority character.

This greedy rule guarantees a valid result for all valid inputs where a and b are each at most 100 (the constraint range). The key observation is that placing two of the majority followed by one of the minority is always safe and always makes progress toward balancing the counts.

Walking through it step by step

Let's trace through a = 4, b = 1. The character 'a' is the majority, so we place two a's, then a b, then continue with whatever is left.

The greedy rule produced "aabaa", which uses all 4 a's and 1 b with no triple violations. At each step, we placed two of the majority when possible and switched to the minority when we had to.

The greedy solution

def strWithout3a3b(a, b):
    result = []
    while a > 0 or b > 0:
        if len(result) >= 2 and result[-1] == result[-2]:
            if result[-1] == 'a':
                result.append('b')
                b -= 1
            else:
                result.append('a')
                a -= 1
        elif a >= b:
            result.append('a')
            a -= 1
        else:
            result.append('b')
            b -= 1
    return ''.join(result)

One loop, one list. Here is what each piece does:

1. The while loop runs until both a and b are exhausted. Each iteration appends exactly one character, so the loop runs a + b times.
2. The first if checks whether the last two characters in the result are the same. If so, we must place the other character to avoid a triple. This is the safety valve.
3. If no triple is imminent, we pick whichever character has more remaining (a >= b means pick 'a'). This greedy choice keeps the counts balanced and avoids building up a surplus that would force triples later.
4. After the loop, we join the list into a string and return it.

Complexity analysis

This is optimal. The output itself is a + b characters long, so you cannot do better than O(a + b) for either time or space.

Building blocks

This problem is built on 2 reusable patterns that CodeBricks drills independently.

1. Greedy character scheduling

The pattern of choosing which character to place next based on remaining counts and a constraint on consecutive repetitions:

while resources_remain():
    if last_two_same():
        place_other_character()
    elif count_a >= count_b:
        place_a()
    else:
        place_b()

This same skeleton solves Reorganize String (no two adjacent characters alike), Task Scheduler (cooldown between identical tasks), and any problem where you interleave resources under a "max consecutive" constraint. The only things that change are the number of resource types and the allowed run length.

2. Run-length constraint checking

The pattern of inspecting the tail of the result to enforce a maximum run length before appending the next element:

if len(result) >= k and all(result[-i] == result[-1] for i in range(1, k)):
    switch_to_different_element()

In this problem, k = 2 (we check the last two characters). In problems like Paint House or encoding constraints, the same idea applies with different values of k. The trick is always the same: look back at the most recent elements to decide what you can place next.

Edge cases

Before submitting, make sure your solution handles these:

• One count is zero a=3, b=0: result is "aaa". Wait, that violates the constraint. But the problem guarantees this will not happen with invalid inputs. When b=0 and a <= 2, the result is just "a" or "aa".
• Equal counts a=3, b=3: the algorithm alternates, producing something like "aababb" or "ababab". Both are valid.
• One count is 1 a=1, b=3: result could be "bbabb" or "bba b". The single minority character is placed to break up the majority's run.
• Counts differ by exactly 1 a=3, b=2: result could be "aabab". The majority gets one extra appearance but never three in a row.
• Large inputs a=100, b=100: the greedy approach handles this in 200 iterations with no issues.

Common mistakes

1. Not checking the last two characters before appending. If you only track counts and ignore what you just placed, you will accidentally create "aaa" or "bbb" when one count is much larger than the other.

2. Always placing exactly one character per turn. This works for equal counts but fails when one count is much larger. You need to place two of the majority character when the counts are unbalanced to avoid being stuck with only majority characters at the end.

3. Forgetting to handle the case where one count reaches zero. Once b hits 0, you can only place a's. If a is still greater than 2, you need to have placed enough b's earlier to break up the a's. The greedy approach handles this naturally, but ad-hoc solutions often miss it.

From understanding to recall

You have read the greedy solution and it makes sense. One loop, one check for the last two characters, one comparison of remaining counts. Clean. But can you write it from scratch in an interview without looking at it?

The details matter: checking result[-1] == result[-2] before the count comparison, decrementing the right counter, and knowing that a >= b means you pick 'a'. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy interleaving loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "build a string with a constraint on consecutive characters" and the code flows out without hesitation.

The greedy character scheduling pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Lemonade Change - Another greedy problem where a simple priority rule replaces brute-force search
• Gas Station - Greedy with running sums and reset logic for circular traversal
• Jump Game - Greedy reachability tracking that avoids exhaustive simulation

CodeBricks breaks the string without AAA or BBB LeetCode problem into its greedy scheduling and run-length constraint building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy interleaving question shows up in your interview, you do not think about it. You just write it.