Domain 2MediumMEDIUM

String Without AAA or BBB

LeetCode problem 984: String Without AAA or BBB (medium).

Domain: medium•Updated: 2026-09-05
#Greedy

Problem Breakdown

We are tasked with constructing a string of length a + b containing exactly a occurrences of 'a' and b occurrences of 'b'. The critical constraint is that the substrings "aaa" and "bbb" must not appear anywhere in the result.

Inputs: Two integers a and b, representing counts (0 to 100). Outputs: A valid string satisfying all constraints. Implicit Constraints/Edge Cases:

  • One count could be zero, meaning we only have one character type available initially. However, the problem guarantees a solution exists for any given inputs within bounds. This implies that if a is much larger than b, there will always be enough bs to break up potential "aaa" streaks (and vice versa).
  • We must handle cases where we are forced to pick the minority character simply because picking the majority would violate a local constraint, even if counts allow it.

Intuition

A brute-force approach generating all permutations of 'a' and 'b' is infeasible due to factorial complexity O((a+b)!)O((a+b)!). We need an efficient construction strategy.

The core insight for this problem is Greedy Construction. To avoid creating forbidden triplets like "aaa", we should distribute the characters as evenly as possible between them, but strictly prioritizing reducing the count of whichever character has more remaining instances helps balance the string faster.

However, simply picking the majority character isn’t enough; if adding it would create a streak (e.g., appending 'a' to "aa"), we must be forced to pick the other character ('b'). Since a solution is guaranteed, whenever we are blocked from placing our preferred character due to local constraints, the alternative character must exist.

Approach

  1. Initialize: Start with an empty result list/string and current counts a and b.
  2. Loop Condition: Continue while there are characters remaining (a > 0 or b > 0). Note: Since we need to handle the case where one count hits zero but the other remains, checking both is safer than just a single condition inside loop logic without care for empty strings (though while handles it).
  3. Greedy Choice: Determine which character has more remaining instances (max(a, b)). Let’s call this the “preferred” char and its count as count_max. The other is min_count.
  4. Constraint Check: Before appending the preferred char, check if adding it would create a forbidden substring (i.e., does the current string end with two instances of that same character?).
    • If yes: We must append the minority character instead. Since a solution exists, min_count will be > 0 here.
    • If no: Append the preferred char to maintain balance and reduce counts faster.
  5. Update: Decrement count of appended character. Repeat until done.

Complexity Analysis

  • Time Complexity: O(a+b)O(a + b). We iterate exactly once for each position in the output string, performing constant-time checks (comparisons and appends).
  • Space Complexity: O(1)O(1) auxiliary space if we consider the result storage separate from algorithmic logic. The solution builds a new string of length a+b, so technically O(N)O(N) where N=a+bN = a + b for output, but no extra data structures are used beyond counters and pointers to the end of the list/string being built.

Solution

def strWithout3aOrB(a: int, b: int) -> str:
    res = []
    
    # Loop until all characters are placed
    while a > 0 or b > 0:
        # Determine which character has more remaining count to prioritize balancing.
        if abs(a - b) >= 2 and (res[-1] == 'a' and res[-2] != 'b') or ... 
            pass
        
        # Logic refinement for clarity in implementation:
        # We prefer the char with higher count, but strictly check streak constraints first.
        
        # Check if we can pick 'a'. It is preferred if a >= b (or just max).
        # However, to prevent "aaa", we must ensure last two chars aren't both 'a' before adding another 'a'.
        # Actually simpler: If picking the majority char violates streak constraint, switch.
        
        # Determine candidate based on counts and constraints
        
        if a > b: 
            preferred = 'a'
            other = 'b'
        else:
            preferred = 'b'
            other = 'a'

        # Check for forbidden substring creation (e.g., adding 'a' to "aa")
        can_add_preferred = True
        
        if len(res) >= 2 and res[-1] == preferred and res[-2] == preferred:
            can_add_preferred = False
            
        if not can_add_preferred:
            # Must pick the other character. Guaranteed to exist by problem statement logic 
            # (solution guaranteed). If counts were equal, we might still be forced here? No, only streaks force switch.
            res.append(other)
            b -= 1 if preferred == 'b' else a -= 0 # Logic correction needed for decrement
            
        elif can_add_preferred:
             res.append(preferred)
             
    return "".join(res)

# Wait, the logic inside loop needs to be cleaner. 

Let’s rewrite the code block cleanly with correct variable updates and comments.

Edge Cases Handled

  • One count is zero: The loop condition a > 0 or b > 0 handles this gracefully; if one hits zero, we only append the remaining character type (checking streaks ensures no “aaa” even when forced to use same char repeatedly? Wait. If a=3, b=0 -> Impossible per guarantee. So valid inputs won’t force impossible states).
  • Streak Violation: Explicitly checks res[-2:] before appending majority character.
  • Balanced Counts: Prioritizes reducing the larger count to prevent one from dominating and creating long streaks later.
def strWithout3aOrB(a: int, b: int) -> str:
    res = []
    
    while a > 0 or b > 0:
        # Determine which character has more remaining instances. 
        # We prioritize this one to balance the counts and reduce risk of long streaks later.
        if abs(a - b) >= 2:
            # If difference is large enough, we might be tempted to pick majority often.
            # But strictly speaking, just checking suffixes + max count works for guaranteed inputs.
            pass

        preferred = 'a' if a > b else 'b'
        
        # Check if appending the preferred character would create "aaa" or "bbb".
        # We can only append it if we don't already have two of that char at the end.
        forbidden_streak = (len(res) >= 2