# String Without AAA or BBB
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/string-without-aaa-or-bbb)
Canonical: https://scaleengineer.com/dsa/problems/string-without-aaa-or-bbb
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Zalando](https://scaleengineer.com/companies/zalando)
---
## 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 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`.

# Approaches
## Backtracking Search
This approach frames the problem as a search for a valid path in a decision tree. It explores all possible ways to construct the string by recursively adding 'a' or 'b' at each step, while respecting the problem's constraints. It backtracks if a path leads to an invalid state (like creating 'aaa' or 'bbb'). Since a solution is guaranteed to exist, this method will eventually find one.
**Time:** O(2^(a+b)). In the worst case, the algorithm might explore a large portion of the search tree. The depth of the recursion is `a+b`, and at each level, there can be up to two branches. This is highly inefficient. · **Space:** O(a+b). The recursion depth can go up to `a+b`. The `StringBuilder` also holds up to `a+b` characters. Therefore, the space complexity is dominated by the recursion stack and the builder, resulting in O(a+b).
**Pros:** Conceptually simple to understand as it directly models the problem as a search.; Guaranteed to find a solution if one exists.
**Cons:** Extremely inefficient due to its exponential time complexity.; Impractical for the given constraints (a, b <= 100) and would likely result in a 'Time Limit Exceeded' error.; High space usage due to recursion depth and repeated string concatenations.
### Explanation
We can define a recursive function that tries to build the string character by character. The state of our recursion will be the number of 'a's and 'b's remaining to be placed, and the string built so far. The function will try to append 'a' if valid, and if that path doesn't lead to a full solution, it will try to append 'b'. Since the problem guarantees a solution exists, one of these paths will succeed.

```java
class Solution {
    public String strWithout3a3b(int a, int b) {
        // Using a StringBuilder for better performance than string concatenation.
        return find(a, b, new StringBuilder());
    }

    private String find(int a, int b, StringBuilder current) {
        if (a < 0 || b < 0) { // Should not happen with proper checks
            return null;
        }
        if (a == 0 && b == 0) {
            return current.toString();
        }

        // Try adding 'a'
        int len = current.length();
        if (a > 0 && (len < 2 || current.charAt(len - 1) != 'a' || current.charAt(len - 2) != 'a')) {
            current.append('a');
            String result = find(a - 1, b, current);
            if (result != null) return result;
            current.deleteCharAt(current.length() - 1); // backtrack
        }

        // Try adding 'b'
        len = current.length();
        if (b > 0 && (len < 2 || current.charAt(len - 1) != 'b' || current.charAt(len - 2) != 'b')) {
            current.append('b');
            String result = find(a, b - 1, current);
            if (result != null) return result;
            current.deleteCharAt(current.length() - 1); // backtrack
        }

        return null;
    }
}
```
### Algorithm
*   **Base Case:** If both remaining 'a's (`a_rem`) and 'b's (`b_rem`) are 0, we have successfully constructed a valid string. Return the current string.
*   **Recursive Step:** At each step, we have two potential choices: append 'a' or append 'b'.
*   **Choice 'a':** If `a_rem > 0` and appending 'a' does not create the substring 'aaa' (i.e., the last two characters of the current string are not 'aa'), we make a recursive call with `a_rem - 1`.
*   If the recursive call for 'a' finds a solution (doesn't return a failure indicator), we return that solution immediately.
*   **Choice 'b':** If `b_rem > 0` and appending 'b' does not create 'bbb', we make a recursive call with `b_rem - 1`.
*   If the recursive call for 'b' finds a solution, we return it.
*   If neither choice leads to a solution from the current state, we backtrack by returning a failure indicator (e.g., `null`).

## Greedy Approach
A much more efficient approach is to build the string greedily from left to right. At each step, we decide which character to append based on a simple set of rules that ensures we never violate the conditions while making progress. The core idea is to prioritize appending the character that is currently more abundant, unless doing so would create a forbidden substring ('aaa' or 'bbb').
**Time:** O(a + b). The loop runs exactly `a + b` times to build the string. Inside the loop, operations like checking the last two characters, appending to a `StringBuilder`, and decrementing a counter are all O(1) (amortized for `StringBuilder`). · **Space:** O(a + b). This space is required for the `StringBuilder` to construct the output string. This is optimal as the output string itself has a length of `a + b`.
**Pros:** Highly efficient with linear time complexity.; Simple and elegant logic.; Guaranteed to produce a correct result given the problem's constraints.
**Cons:** The correctness of the greedy choice is not immediately obvious without reasoning about the problem constraints (i.e., that a valid solution is always possible, which implies `a <= 2(b+1)` and `b <= 2(a+1)`).
### Explanation
This greedy strategy works because the problem guarantees that a solution exists. This implies that we will never reach a 'dead end' state where we are forced to append a character that violates the rules (e.g., needing to append 'b' because the string ends in 'aa', but having no 'b's left). The greedy choice of using the more frequent character helps to keep the remaining counts of 'a's and 'b's balanced, steering away from such impossible states.

```java
class Solution {
    public String strWithout3a3b(int a, int b) {
        StringBuilder res = new StringBuilder(a + b);
        while (a > 0 || b > 0) {
            int len = res.length();
            // Check if we are forced to write a specific character
            if (len >= 2 && res.charAt(len - 1) == res.charAt(len - 2)) {
                if (res.charAt(len - 1) == 'a') {
                    // Last two are 'aa', must write 'b'
                    res.append('b');
                    b--;
                } else {
                    // Last two are 'bb', must write 'a'
                    res.append('a');
                    a--;
                }
            } else {
                // Free choice, append the character with the larger remaining count
                if (a > b) {
                    res.append('a');
                    a--;
                } else {
                    res.append('b');
                    b--;
                }
            }
        }
        return res.toString();
    }
}
```
### Algorithm
*   Initialize an empty `StringBuilder` to construct the result string.
*   Loop until we have used all 'a's and 'b's (i.e., the result string length is `a+b`).
*   In each iteration, decide whether to append 'a' or 'b'.
*   **Decision Rule:**
    *   If the last two characters added were 'aa', we are forced to append 'b'.
    *   If the last two characters added were 'bb', we are forced to append 'a'.
    *   Otherwise, we have a free choice. We greedily append the character that has a higher remaining count. If `a > b`, we append 'a'. Otherwise (`b >= a`), we append 'b'.
*   Append the chosen character to the `StringBuilder` and decrement its corresponding counter.
*   After the loop finishes, return the constructed string.

# Solutions
### Java

```java
class Solution {
public
  String strWithout3a3b(int a, int b) {
    StringBuilder ans = new StringBuilder();
    while (a > 0 && b > 0) {
      if (a > b) {
        ans.append("aab");
        a -= 2;
        b -= 1;
      } else if (a < b) {
        ans.append("bba");
        a -= 1;
        b -= 2;
      } else {
        ans.append("ab");
        --a;
        --b;
      }
    }
    if (a > 0) {
      ans.append("a".repeat(a));
    }
    if (b > 0) {
      ans.append("b".repeat(b));
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution { public: string strWithout3a3b ( int a , int b ) { string ans ; while ( a && b ) { if ( a > b ) { ans += "aab" ; a -= 2 ; b -= 1 ; } else if ( a < b ) { ans += "bba" ; a -= 1 ; b -= 2 ; } else { ans += "ab" ; -- a ; -- b ; } } if ( a ) ans += string ( a , 'a' ); if ( b ) ans += string ( b , 'b' ); return ans ; } };
```

### Python

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