LeetCode 984 - String Without AAA or BBB

The problem gives us two integers, a and b, representing how many 'a' characters and 'b' characters we must place into a string.

leetcodemediumstringgreedy

LeetCode Problem 984

Difficulty: 🟡 Medium
Topics: String, Greedy

Solution

Problem Understanding

The problem gives us two integers, a and b, representing how many 'a' characters and 'b' characters we must place into a string. Our task is to construct any valid string of length a + b such that:

  • Exactly a characters are 'a'
  • Exactly b characters are 'b'
  • The substring "aaa" never appears
  • The substring "bbb" never appears

The output does not need to be unique. Any valid arrangement is acceptable.

The key difficulty comes from balancing the characters so that no character appears three times consecutively. A naive approach might simply append all 'a' characters followed by all 'b' characters, but that would immediately violate the constraint whenever either count is at least 3.

For example:

  • If a = 4 and b = 1, the string "aaaab" is invalid because it contains "aaa".
  • A valid arrangement would instead spread the characters out, such as "aabaa".

The constraints are relatively small:

  • 0 <= a, b <= 100

Because the input size is tiny, even moderately inefficient algorithms could work. However, the challenge is more about constructing the string correctly than about handling large input sizes.

An important guarantee is provided by the problem statement:

It is guaranteed such a string exists.

This means we never need to handle impossible cases. We can focus entirely on building a valid arrangement.

Several edge cases are important:

  • One character count may be much larger than the other.
  • One count may be zero.
  • The counts may already be balanced.
  • We must ensure that adding characters greedily never accidentally creates three consecutive identical letters.

The core challenge is deciding which character to place next while preserving validity throughout the construction process.

Approaches

Brute Force Approach

A brute force solution would generate every possible string of length a + b containing exactly a 'a' characters and b 'b' characters. For each generated string, we would check whether it contains "aaa" or "bbb".

This approach is correct because it exhaustively examines every possible arrangement. Eventually, it will find a valid string since the problem guarantees one exists.

However, this method is extremely inefficient. The number of possible strings is:

$\binom{a+b}{a}$

This grows exponentially as the input size increases. Even though the constraints are small, generating all combinations is unnecessary and inefficient.

Optimal Greedy Approach

The key insight is that we should always try to place the character with the larger remaining count, but only if doing so does not create three consecutive identical characters.

Why does this work?

If one character appears much more frequently than the other, we must distribute it carefully throughout the string. Delaying placement of the more frequent character can make it impossible to place later without violating the constraints.

The greedy strategy therefore becomes:

  • Prefer the character with the larger remaining count.
  • Before appending, check whether the last two characters are already the same.
  • If appending the preferred character would create three consecutive identical characters, append the other character instead.

Because the problem guarantees a valid solution exists, this strategy always succeeds.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(a+b)) O(a+b) Generates all possible valid permutations
Optimal O(a+b) O(a+b) Greedily builds a valid string incrementally

Algorithm Walkthrough

  1. Initialize an empty result list.

We use a list instead of repeatedly concatenating strings because appending to a list is efficient in both Python and Go. 2. Continue building the string while either a or b remains greater than zero.

At each iteration, we decide whether to append 'a' or 'b'. 3. Check the last two characters of the current result.

If the last two characters are identical, then appending the same character again would create an invalid substring.

For example:

  • Current result: "aa"
  • Appending another 'a' would create "aaa"
  1. If the last two characters are the same:
  • We are forced to append the opposite character.
  • This prevents three consecutive identical letters.
  1. Otherwise, choose the character with the larger remaining count.

This is the greedy part of the algorithm.

If a > b, append 'a'.

Otherwise, append 'b'.

The reasoning is that the more frequent character is harder to place later, so we should use it whenever possible. 6. Decrease the corresponding counter after appending.

If we append 'a', decrement a.

If we append 'b', decrement b. 7. Repeat until both counters reach zero. 8. Convert the result list into a string and return it.

Why it works

The algorithm maintains an important invariant:

At no point does the constructed prefix contain "aaa" or "bbb".

Whenever two consecutive identical characters already exist, the algorithm is forced to place the opposite character. Otherwise, it greedily places the more frequent character to avoid future imbalance problems.

Because the problem guarantees that a valid solution exists, this greedy strategy can always complete successfully without getting stuck.

Python Solution

class Solution:
    def strWithout3a3b(self, a: int, b: int) -> str:
        result = []

        while a > 0 or b > 0:
            n = len(result)

            # If the last two characters are the same,
            # we must place the opposite character.
            if n >= 2 and result[-1] == result[-2]:
                if result[-1] == 'a':
                    result.append('b')
                    b -= 1
                else:
                    result.append('a')
                    a -= 1
            else:
                # Otherwise, greedily place the character
                # with the larger remaining count.
                if a >= b and a > 0:
                    result.append('a')
                    a -= 1
                else:
                    result.append('b')
                    b -= 1

        return "".join(result)

The implementation follows the greedy algorithm directly.

The result list stores the characters as we build the string. Using a list avoids repeated string reallocations.

Inside the loop, we first examine the last two characters. If they are identical, we are forced to place the opposite character to avoid creating three consecutive letters.

If the last two characters are not identical, we greedily append the character with the larger remaining count. This helps distribute the more frequent character as early as possible.

After appending a character, the corresponding counter is decremented. The loop continues until all characters have been used.

Finally, "".join(result) converts the character list into the final string.

Go Solution

func strWithout3a3b(a int, b int) string {
	result := make([]byte, 0)

	for a > 0 || b > 0 {
		n := len(result)

		// If the last two characters are the same,
		// we must place the opposite character.
		if n >= 2 && result[n-1] == result[n-2] {
			if result[n-1] == 'a' {
				result = append(result, 'b')
				b--
			} else {
				result = append(result, 'a')
				a--
			}
		} else {
			// Otherwise, greedily place the character
			// with the larger remaining count.
			if a >= b && a > 0 {
				result = append(result, 'a')
				a--
			} else {
				result = append(result, 'b')
				b--
			}
		}
	}

	return string(result)
}

The Go implementation mirrors the Python logic closely.

Instead of a Python list, Go uses a []byte slice for efficient character appending. Since strings in Go are immutable, building the result with a byte slice is more efficient than repeated string concatenation.

The final conversion from []byte to string is done using string(result).

No special handling for integer overflow is necessary because the constraints are extremely small.

Worked Examples

Example 1

Input:

a = 1, b = 2

Initial state:

Step Result a b Action
1 "" 1 2 Choose 'b' because b > a
2 "b" 1 1 Choose 'a' because counts equal
3 "ba" 0 1 Choose 'b'

Final result:

"bab"

This string:

  • Contains one 'a'
  • Contains two 'b'
  • Contains no "aaa"
  • Contains no "bbb"

Example 2

Input:

a = 4, b = 1

Initial state:

Step Result a b Action
1 "" 4 1 Append 'a'
2 "a" 3 1 Append 'a'
3 "aa" 2 1 Forced to append 'b'
4 "aab" 2 0 Append 'a'
5 "aaba" 1 0 Append 'a'

Final result:

"aabaa"

The algorithm correctly prevents "aaa" from appearing.

Complexity Analysis

Measure Complexity Explanation
Time O(a+b) Each iteration appends exactly one character
Space O(a+b) The output string stores all characters

The algorithm processes each character exactly once. Since the final string contains a + b characters, the total runtime is linear in the output size.

The extra space usage is also linear because we store the constructed string in memory.

Test Cases

class Solution:
    def strWithout3a3b(self, a: int, b: int) -> str:
        result = []

        while a > 0 or b > 0:
            n = len(result)

            if n >= 2 and result[-1] == result[-2]:
                if result[-1] == 'a':
                    result.append('b')
                    b -= 1
                else:
                    result.append('a')
                    a -= 1
            else:
                if a >= b and a > 0:
                    result.append('a')
                    a -= 1
                else:
                    result.append('b')
                    b -= 1

        return "".join(result)

def is_valid(s, a, b):
    return (
        len(s) == a + b and
        s.count('a') == a and
        s.count('b') == b and
        'aaa' not in s and
        'bbb' not in s
    )

sol = Solution()

# Provided example 1
s = sol.strWithout3a3b(1, 2)
assert is_valid(s, 1, 2)

# Provided example 2
s = sol.strWithout3a3b(4, 1)
assert is_valid(s, 4, 1)

# Balanced counts
s = sol.strWithout3a3b(3, 3)
assert is_valid(s, 3, 3)

# More a's than b's
s = sol.strWithout3a3b(5, 2)
assert is_valid(s, 5, 2)

# More b's than a's
s = sol.strWithout3a3b(2, 5)
assert is_valid(s, 2, 5)

# Single character
s = sol.strWithout3a3b(1, 0)
assert is_valid(s, 1, 0)

# Single opposite character
s = sol.strWithout3a3b(0, 1)
assert is_valid(s, 0, 1)

# Larger balanced case
s = sol.strWithout3a3b(50, 50)
assert is_valid(s, 50, 50)

# Larger unbalanced case
s = sol.strWithout3a3b(70, 30)
assert is_valid(s, 70, 30)

# Minimal empty case
s = sol.strWithout3a3b(0, 0)
assert is_valid(s, 0, 0)
Test Why
(1, 2) Validates simple asymmetric input
(4, 1) Ensures greedy logic avoids "aaa"
(3, 3) Tests balanced counts
(5, 2) Tests larger imbalance toward 'a'
(2, 5) Tests larger imbalance toward 'b'
(1, 0) Tests single-character output
(0, 1) Tests opposite single-character output
(50, 50) Tests large balanced input
(70, 30) Tests large unbalanced input
(0, 0) Tests empty-string case

Edge Cases

One important edge case occurs when one character count is much larger than the other, such as a = 7 and b = 2. A naive implementation might repeatedly append 'a' because it has the larger count, eventually producing "aaa". The greedy solution avoids this by checking the last two characters before every append. Once two 'a' characters appear consecutively, the algorithm is forced to insert 'b'.

Another important edge case occurs when one count is zero. For example, a = 1 and b = 0. The algorithm must still work correctly without attempting to append nonexistent characters. The implementation handles this naturally because it only decrements counts after confirming that a character is available.

A third edge case occurs when the counts are perfectly balanced, such as a = 3 and b = 3. In this scenario, many valid strings exist. The algorithm still behaves correctly because when counts are equal, it consistently chooses one character first while continuing to enforce the no-three-consecutive rule.

Finally, the empty input case a = 0 and b = 0 deserves attention. The algorithm immediately exits the loop and returns an empty string, which is valid because all constraints are satisfied.