String Without AAA or BBB

Problem Statement

The goal is to generate a string s of length a + b, where a represents the exact number of 'a' characters and b the exact number of 'b' characters in the string. The string must be formatted such that it does not contain the substring 'aaa' or 'bbb', ensuring that no three consecutive identical characters are present. The challenge lies in structuring the string to meet these criteria while utilizing all given 'a's and 'b's.

Examples

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 and Intuition

When designing a string s that includes a specific number of 'a' and 'b' characters without forming the substrings 'aaa' or 'bbb', here's a logical strategy:

1. Initialization: Start by identifying which character is in the majority (a or b). This will help in deciding the primary looping character.

2. Greedy Construction: Use a greedy approach where you alternately place characters, but avoid placing more than two of the same character consecutively:

   • If a > b, start with 'a'. For every 'a' added, if possible add a 'b' to break a potential sequence of three 'a' characters.

   • If b > a, start with 'b'. Similarly, add 'a' after every two 'b's to prevent the formation of 'bbb'.

3. Balance Characters: Make sure that after inserting two same characters, insert the opposite character if there are remaining counts of the opposite character. This helps in balancing out the counts and maintaining the required format.

4. Edge Cases:

   • If a or b equals zero, the resultant string will simply be the repeated character of the non-zero count but constrained to groups of at most two (e.g., "aa" or "bb").

5. Handling Equal Numbers: If a is equal to b, alternate them, like "ababab...". This automatically avoids the appearance of three consecutive same characters.

Examples are instrumental in understanding and verifying this approach:

• For a = 1, b = 2: Starting with the majority, the string could be "bba", "bab" or "abb".

• For a = 4, b = 1: The approach would suggest starting with 'a', then inserting a 'b' to prevent three 'a's in a row, resulting in "aabaa".

This methodology provides a structured way to construct the string while adhering to the constraints on consecutive characters.

Solutions

class Solution {
    public String buildString(int countA, int countB) {
        StringBuilder result = new StringBuilder();

        while (countA > 0 || countB > 0) {
            boolean appendA = false;
            int length = result.length();
            if (length >= 2 && result.charAt(length-1) == result.charAt(length-2)) {
                if (result.charAt(length-1) == 'b')
                    appendA = true;
            } else {
                if (countA >= countB)
                    appendA = true;
            }

            if (appendA) {
                countA--;
                result.append('a');
            } else {
                countB--;
                result.append('b');
            }
        }

        return result.toString();
    }
}