984. String Without AAA or BBB Solution

The 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.

Approach overview

Problem Overview: You are given two integers a and b representing how many times characters 'a' and 'b' must appear in a string. The goal is to construct any valid string that uses all characters while avoiding the substrings "aaa" and "bbb".

Approach 1: Greedy Approach with Alternating Strategy (O(a+b) time, O(1) space)

This approach builds the string one character at a time using a greedy rule. At each step, compare the remaining counts of a and b. Prefer the character with the larger remaining count, but only if adding it will not create three consecutive identical characters. If the last two characters in the result are the same, force the other character even if its count is smaller. The key insight is that always consuming the more frequent character keeps the distribution balanced while the consecutive check prevents invalid triples.

You maintain a growing result buffer and check the last two characters before appending. Each iteration reduces either a or b, so the loop runs exactly a + b times. This greedy constraint handling ensures the string never forms "aaa" or "bbb". The algorithm uses constant auxiliary memory besides the output string. This pattern commonly appears in greedy scheduling and balancing problems.

Approach 2: Interleaving Strategy (O(a+b) time, O(1) space)

The interleaving strategy first determines which character occurs more frequently. Suppose a > b. You place blocks like "aab" repeatedly while the difference between counts is large, then switch to alternating patterns like "ab" once the counts become closer. The idea is to distribute the dominant character across the entire string so it never forms three consecutive occurrences.

This technique effectively spreads the majority character in controlled groups of at most two before inserting the minority character. You continue until one character runs out, then append the remaining characters while respecting the two‑character limit. Because each character is appended once, the runtime remains linear in the final string length. This approach is essentially a structured version of the greedy idea and works well for problems involving constrained string construction and pattern avoidance.

Recommended for interviews: The greedy alternating strategy is what interviewers typically expect. It demonstrates that you can enforce constraints dynamically while building the result. Explaining why you prioritize the character with the larger remaining count—and how the last two characters prevent illegal triples—shows strong reasoning about greedy algorithms. The interleaving approach also works, but the dynamic greedy check is usually clearer and easier to implement under interview pressure.

Approach 1: Greedy Approach with Alternating Strategy

This approach constructs the string by always choosing the majority character until we need to switch to prevent three consecutive characters.

Steps:

Determine which character ('a' or 'b') is more prevalent.
Alternate placing two of the more prevalent character with one of the less prevalent character.
Continue this until all characters are used up, ensuring that neither 'aaa' nor 'bbb' are formed.

Python

def strWithout3a3b(a: int, b: int) -> str:
    res = []
    while a > 0 or b > 0:
        writeA = False
        if len(res) >= 2 and res[-1] == res[-2]:
            if res[-1] == 'b':
                writeA = True
        else:
            if a >= b:
                writeA = True

        if writeA:
            res.append('a')
            a -= 1
        else:
            res.append('b')
            b -= 1
    return ''.join(res)

# Example usage
print(strWithout3a3b(4, 1))

Java

public class StringWithoutAAAorBBB {
    public static String strWithout3a3b(int a, int b) {
        StringBuilder res = new StringBuilder();
        while (a > 0 || b > 0) {
            boolean writeA = false;
            int n = res.length();
            if (n >= 2 && res.charAt(n-1) == res.charAt(n-2)) {
                if (res.charAt(n-1) == 'b') writeA = true;
            } else {
                if (a >= b) writeA = true;
            }

            if (writeA) {
                res.append('a');
                a--;
            } else {
                res.append('b');
                b--;
            }
        }
        return res.toString();
    }

    public static void main(String[] args) {
        int a = 4, b = 1;
        System.out.println(strWithout3a3b(a, b));
    }
}

C++

#include <iostream>
#include <string>

std::string strWithout3a3b(int a, int b) {
    std::string res;
    while (a > 0 || b > 0) {
        bool writeA = false;
        int n = res.size();
        if (n >= 2 && res[n-1] == res[n-2]) {
            if (res[n-1] == 'b') writeA = true;
        } else {
            if (a >= b) writeA = true;
        }

        if (writeA) {
            res += 'a';
            a--;
        } else {
            res += 'b';
            b--;
        }
    }
    return res;
}

int main() {
    int a = 4, b = 1;
    std::cout << strWithout3a3b(a, b) << std::endl;
    return 0;
}

JavaScript

function strWithout3a3b(a, b) {
    let res = [];
    while (a > 0 || b > 0) {
        let writeA = false;
        let n = res.length;
        if (n >= 2 && res[n - 1] === res[n - 2]) {
            if (res[n - 1] === 'b') writeA = true;
        } else {
            if (a >= b) writeA = true;
        }

        if (writeA) {
            res.push('a');
            a--;
        } else {
            res.push('b');
            b--;
        }
    }
    return res.join('');
}

console.log(strWithout3a3b(4, 1));

#include <stdio.h>
#include <string.h>

char* strWithout3a3b(int a, int b) {
    static char result[201];
    int index = 0;
    while (a > 0 || b > 0) {
        int useA = 0;
        if (index > 1 && result[index-1] == result[index-2]) {
            useA = result[index-1] == 'b';
        } else {
            useA = a >= b;
        }
        if (useA) {
            result[index++] = 'a';
            a--;
        } else {
            result[index++] = 'b';
            b--;
        }
    }
    result[index] = '\0';
    return result;
}

int main() {
    int a = 4, b = 1;
    printf("%s\n", strWithout3a3b(a, b));
    return 0;
}

using System;
using System.Text;

public class Solution {
    public string StrWithout3a3b(int a, int b) {
        StringBuilder sb = new StringBuilder();
        while (a > 0 || b > 0) {
            bool writeA = false;
            int n = sb.Length;
            if (n >= 2 && sb[n-1] == sb[n-2]) {
                if (sb[n-1] == 'b') writeA = true;
            } else {
                if (a >= b) writeA = true;
            }

            if (writeA) {
                sb.Append('a');
                a--;
            } else {
                sb.Append('b');
                b--;
            }
        }
        return sb.ToString();
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.StrWithout3a3b(4, 1));
    }
}

The Python solution builds the string using a list (for efficient append operations) and later converts it to a string. The choice of appending 'a' or 'b' is managed to avoid three consecutive identical characters and to balance the quantity.

Complexity

Time Complexity: O(a + b) as we process each character individually.
Space Complexity: O(a + b) for storing the result in a list.

Try this approach in the editor

Approach 2: Interleaving Strategy

This approach leverages an interleaving strategy to distribute characters evenly and avoid consecutive identical sequences.

Steps:

Always append one of the more frequent character followed by the less frequent one until one type is exhausted.
Finish by appending remaining characters in such a way that no prohibited sequence occurs.

Python

def strWithout3a3b(a: int, b: int) -> str:
    result = []
    while a > 0 or b > 0:
        if a > b:
            if a > 0: result.append('a'); a -= 1
            if a > 0: result.append('a'); a -= 1
            if b > 0: result.append('b'); b -= 1
        else:
            if b > 0: result.append('b'); b -= 1
            if b > 0: result.append('b'); b -= 1
            if a > 0: result.append('a'); a -= 1
    return ''.join(result)

print(strWithout3a3b(4, 1))

Java

public class Solution {
    public String strWithout3a3b(int a, int b) {
        StringBuilder result = new StringBuilder();
        while (a > 0 || b > 0) {
            if (a > b) {
                if (a > 0) { result.append("a"); a--; }
                if (a > 0) { result.append("a"); a--; }
                if (b > 0) { result.append("b"); b--; }
            } else {
                if (b > 0) { result.append("b"); b--; }
                if (b > 0) { result.append("b"); b--; }
                if (a > 0) { result.append("a"); a--; }
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.strWithout3a3b(4, 1));
    }
}

C++

#include <iostream>
#include <string>

std::string strWithout3a3b(int a, int b) {
    std::string result;
    while (a > 0 || b > 0) {
        if (a > b) {
            if (a > 0) { result += 'a'; a--; }
            if (a > 0) { result += 'a'; a--; }
            if (b > 0) { result += 'b'; b--; }
        } else {
            if (b > 0) { result += 'b'; b--; }
            if (b > 0) { result += 'b'; b--; }
            if (a > 0) { result += 'a'; a--; }
        }
    }
    return result;
}

int main() {
    std::cout << strWithout3a3b(4, 1) << std::endl;
    return 0;
}

JavaScript

function strWithout3a3b(a, b) {
    let result = [];
    while (a > 0 || b > 0) {
        if (a > b) {
            if (a > 0) { result.push('a'); a--; }
            if (a > 0) { result.push('a'); a--; }
            if (b > 0) { result.push('b'); b--; }
        } else {
            if (b > 0) { result.push('b'); b--; }
            if (b > 0) { result.push('b'); b--; }
            if (a > 0) { result.push('a'); a--; }
        }
    }
    return result.join('');
}

console.log(strWithout3a3b(4, 1));

#include <stdio.h>

char* strWithout3a3b(int a, int b) {
    static char result[201];
    int index = 0;
    while (a > 0 || b > 0) {
        if (a > b) {
            if (a > 0) { result[index++] = 'a'; a--; }
            if (a > 0) { result[index++] = 'a'; a--; }
            if (b > 0) { result[index++] = 'b'; b--; }
        } else {
            if (b > 0) { result[index++] = 'b'; b--; }
            if (b > 0) { result[index++] = 'b'; b--; }
            if (a > 0) { result[index++] = 'a'; a--; }
        }
    }
    result[index] = '\0';
    return result;
}

int main() {
    int a = 4, b = 1;
    printf("%s\n", strWithout3a3b(a, b));
    return 0;
}

using System;
using System.Text;

public class Solution {
    public string StrWithout3a3b(int a, int b) {
        StringBuilder result = new StringBuilder();
        while (a > 0 || b > 0) {
            if (a > b) {
                if (a > 0) { result.Append('a'); a--; }
                if (a > 0) { result.Append('a'); a--; }
                if (b > 0) { result.Append('b'); b--; }
            } else {
                if (b > 0) { result.Append('b'); b--; }
                if (b > 0) { result.Append('b'); b--; }
                if (a > 0) { result.Append('a'); a--; }
            }
        }
        return result.ToString();
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.StrWithout3a3b(4, 1));
    }
}

This Python solution constructs the required string using a consistent interleaving pattern that ensures no 'aaa' or 'bbb' occurs by alternating the placement of 'a's and 'b's controlled by their counts.

Complexity

Time Complexity: O(a + b) for iterating through available characters.
Space Complexity: O(a + b) for producing the concatenated result.

Try this approach in the editor

Approach 3: Default Approach

func strWithout3a3b(a int, b int) string {
	var ans strings.Builder
	for a > 0 && b > 0 {
		if a > b {
			ans.WriteString("aab")
			a -= 2
			b -= 1
		} else if a < b {
			ans.WriteString("bba")
			a -= 1
			b -= 2
		} else {
			ans.WriteString("ab")
			a--
			b--
		}
	}
	if a > 0 {
		ans.WriteString(strings.Repeat("a", a))
	}
	if b > 0 {
		ans.WriteString(strings.Repeat("b", b))
	}
	return ans.String()
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach with Alternating Strategy	Time Complexity: O(a + b) as we process each character individually. Space Complexity: O(a + b) for storing the result in a list.
Interleaving Strategy	Time Complexity: O(a + b) for iterating through available characters. Space Complexity: O(a + b) for producing the concatenated result.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy Approach with Alternating Strategy	O(a+b)	O(1)	General case; easiest interview implementation with dynamic constraint checks
Interleaving Strategy	O(a+b)	O(1)	When constructing structured patterns like "aab" or "bba" to distribute the majority character

Frequently asked questions

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.

String Without AAA or BBB solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Alternating Strategy

Approach 2: Interleaving Strategy

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

String Without AAA or BBB solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Alternating Strategy

Approach 2: Interleaving Strategy

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems