String Without AAA or BBB

Problem Description

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.

Key Insights

• The string must be constructed in a way that prevents three consecutive as or bs.
• A greedy approach can be used to balance the characters based on their counts.
• Depending on whether a is greater than b or vice versa, we can decide the order of placing the characters.

Space and Time Complexity

Time Complexity: O(a + b)
Space Complexity: O(1) (the string is constructed in place)

Solution

To solve the problem, we can use a greedy algorithm to construct the string by repeatedly adding the character with the higher remaining count. We ensure that we do not add three consecutive characters of the same type:

1. Compare the counts of a and b.
2. Append up to two of the character with the higher count followed by one of the other character, if available.
3. Repeat until all characters are added.

The data structure used here is a simple string builder (or accumulator) that collects the characters as they are determined.

Code Solutions