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

| Requirement | Meaning |
|---|---|
| Length | `s.length == a + b` |
| Count of `a` | `s` contains exactly `a` letters `'a'` |
| Count of `b` | `s` contains exactly `b` letters `'b'` |
| Forbidden substring | `s` must not contain `"aaa"` |
| Forbidden substring | `s` must not contain `"bbb"` |

The problem guarantees that a valid answer exists.

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `a` and `b` |
| Output | Any valid string |
| Allowed characters | Only `'a'` and `'b'` |
| Main rule | No three equal consecutive characters |

Function shape:

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

## Examples

Example 1:

```python
a = 1
b = 2
```

Valid answers include:

```python
"abb"
"bab"
"bba"
```

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

Example 2:

```python
a = 4
b = 1
```

One valid answer is:

```python
"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"`.

```python
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:

```python
"aa"
```

then the next character cannot be `'a'`.

It must be `'b'`.

Similarly, if the current result ends with:

```python
"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`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We append one character per step |
| Space | `O(n)` | The answer list stores the result |

## Implementation

```python
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:

```python
answer = []
```

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

The loop continues until all characters are used:

```python
while a > 0 or b > 0:
```

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

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

we must append `'b'`:

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

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

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

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

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

At the end, convert the list into a string:

```python
return "".join(answer)
```

## Testing

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

```python
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()
```

| Test | Why |
|---|---|
| `(1, 2)` | Basic case with more `'b'` |
| `(4, 1)` | More `'a'` than `'b'` |
| `(2, 5)` | Larger imbalance |
| `(0, 2)` | Only one character type, still valid |
| `(3, 3)` | Equal counts |