LeetCode 2038 - Remove Colored Pieces if Both Neighbors are the Same Color

This problem describes a two-player game played on a line of colored pieces. The input colors is a string representing these pieces, where each character is either 'A' or 'B'. Alice always moves first and can only remove 'A' pieces that are surrounded on both sides by 'A'.

leetcodemediummathstringgreedygame-theory

LeetCode Problem 2038

Difficulty: 🟡 Medium
Topics: Math, String, Greedy, Game Theory

Solution

Problem Understanding

This problem describes a two-player game played on a line of colored pieces. The input colors is a string representing these pieces, where each character is either 'A' or 'B'. Alice always moves first and can only remove 'A' pieces that are surrounded on both sides by 'A'. Bob moves second and can only remove 'B' pieces with the same neighbor rule. Players cannot remove pieces at the edges because they lack two neighbors, and if a player has no valid move on their turn, they lose.

The goal is to determine, assuming both players play optimally, whether Alice can win. The input length can be up to 100,000, so any brute-force simulation of each move is likely too slow. Edge cases include strings that are very short, have no removable pieces for the first player, or have long contiguous blocks of a single color. The problem guarantees that the input string consists only of 'A' and 'B', and we can rely on this to simplify parsing.

The crucial insight is that a piece is removable only if it belongs to a contiguous block of at least three of the same color. The number of such removable pieces in each block determines the maximum moves a player can make. The winner is simply the player who has more possible moves since each move only affects their own color and cannot create new moves for the other player.

Approaches

The brute-force approach would simulate each player's turn, removing pieces one by one and updating the board. At each turn, you would scan the board to find all valid moves, remove one piece, and continue until one player has no moves left. While correct, this approach is far too slow for n = 10^5 because each removal requires scanning the string and updating it, resulting in a time complexity of O(n^2) in the worst case.

The optimal approach uses a greedy counting strategy. Instead of simulating every move, count how many removable 'A' and 'B' pieces exist upfront. This can be done by iterating through the string once and tracking contiguous blocks of the same color. For each block of length L >= 3, there are L - 2 removable pieces. After counting Alice's and Bob's moves, Alice wins if her count is greater than Bob's, because she moves first and can always outlast Bob if she has more available moves.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Simulate each turn by scanning and removing pieces
Optimal O(n) O(1) Count removable pieces in a single pass, compare counts

Algorithm Walkthrough

  1. Initialize two counters alice_moves and bob_moves to zero. These will track the number of pieces Alice and Bob can remove, respectively.
  2. Iterate through the string colors from index 1 to n-2 (excluding edges because pieces there cannot be removed).
  3. For each index i, check if the current character and its neighbors form three consecutive 'A' pieces. If so, increment alice_moves.
  4. Similarly, check if they form three consecutive 'B' pieces. If so, increment bob_moves.
  5. After completing the iteration, compare alice_moves and bob_moves. Alice wins if alice_moves > bob_moves and loses otherwise.
  6. Return the boolean result of this comparison.

Why it works: The key property is that removing a piece in a contiguous block of length ≥3 reduces the block but does not create new opportunities for the other player. Therefore, counting all possible moves upfront accurately predicts the winner under optimal play.

Python Solution

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        alice_moves = 0
        bob_moves = 0
        n = len(colors)
        
        for i in range(1, n - 1):
            if colors[i - 1] == colors[i] == colors[i + 1]:
                if colors[i] == 'A':
                    alice_moves += 1
                else:
                    bob_moves += 1
        
        return alice_moves > bob_moves

This Python implementation iterates once through the string, counting removable 'A' and 'B' pieces using the neighbor rule. It then compares the counts to decide the winner. The use of colors[i - 1] == colors[i] == colors[i + 1] ensures that only pieces with identical neighbors on both sides are counted.

Go Solution

func winnerOfGame(colors string) bool {
    aliceMoves := 0
    bobMoves := 0
    n := len(colors)
    
    for i := 1; i < n-1; i++ {
        if colors[i-1] == colors[i] && colors[i] == colors[i+1] {
            if colors[i] == 'A' {
                aliceMoves++
            } else {
                bobMoves++
            }
        }
    }
    
    return aliceMoves > bobMoves
}

In Go, the logic mirrors Python. Strings are indexed by position, and we count removable 'A' and 'B' pieces in a single pass. No additional data structures are needed, and edge handling is inherently taken care of by iterating from 1 to n-2.

Worked Examples

Example 1: colors = "AAABABB"

Index Segment Count
0-2 'AAA' Alice +1
3-5 'BAB' none
4-6 'ABB' none

Alice moves = 1, Bob moves = 0 → Alice wins → return true.

Example 2: colors = "AA"

String length <3, no removable pieces. Alice moves = 0, Bob moves = 0 → Alice loses → return false.

Example 3: colors = "ABBBBBBBAAA"

Alice moves = 1 (last block 'AAA'), Bob moves = 5 ('BBBBBBB') → Alice moves < Bob moves → Alice loses → return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the string, counting contiguous blocks
Space O(1) Only a few integer counters used, no extra data structures

The optimal solution scales linearly with input size and uses constant memory, making it suitable for strings up to 100,000 characters.

Test Cases

# Provided examples
assert Solution().winnerOfGame("AAABABB") == True  # Alice has one move, Bob none
assert Solution().winnerOfGame("AA") == False      # No moves possible
assert Solution().winnerOfGame("ABBBBBBBAAA") == False  # Bob has more moves

# Edge cases
assert Solution().winnerOfGame("A") == False       # Single piece, no moves
assert Solution().winnerOfGame("B") == False
assert Solution().winnerOfGame("AAA") == True      # Alice can remove one in the middle
assert Solution().winnerOfGame("BBB") == False     # Bob moves second, Alice wins by default
assert Solution().winnerOfGame("AAABBB") == False  # Both have same moves, Alice moves first, Alice wins if moves>Bob
assert Solution().winnerOfGame("AAAABBBBAAA") == True  # Alice has more moves than Bob
assert Solution().winnerOfGame("ABABABABAB") == False  # No blocks of 3, no moves
Test Why
"AAABABB" Tests basic Alice win scenario
"AA" Tests short string edge case
"ABBBBBBBAAA" Tests scenario where Bob has more moves
"AAA" Minimal block Alice can remove
"BBB" Minimal block Bob, Alice moves first
"ABABABABAB" No valid moves for either player

Edge Cases

  1. String length < 3: No piece has two neighbors, so no moves are possible. The solution handles this naturally by iterating only from index 1 to n-2.
  2. All same color: A string like "AAAAA" creates multiple removable pieces. The algorithm counts all blocks of length ≥3 correctly, giving Alice or Bob multiple moves.
  3. Alternating colors with no block ≥3: For a string like "ABABABAB", there are no removable pieces. Alice has zero moves, so she loses by default. The algorithm handles this by simply comparing counts, which are zero for both players.

This approach efficiently and correctly handles all edge cases due to its focus on counting contiguous blocks and ignoring the positions at the edges.