String Without AAA or BBB - Solution & Explanation

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.