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

1. Brute Force

Intuition

We simulate the game turn by turn. Alice looks for a piece 'A' surrounded by two other 'A's and removes it. Then Bob does the same for 'B'. If a player cannot make a move on their turn, they lose. This straightforward simulation mirrors the actual gameplay but is slow because we repeatedly scan and modify the string.

Algorithm

Convert the string to a mutable list.
Alternate turns between Alice ('A') and Bob ('B').
On each turn, scan for a removable piece (one that has the same color on both sides).
If found, remove it and continue. If not found, the current player loses.
Alice wins if Bob cannot move; Bob wins if Alice cannot move.

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        s = list(colors)

        def removeChar(c):
            for i in range(1, len(s) - 1):
                if s[i] != c:
                    continue

                if s[i] == s[i + 1] == s[i - 1]:
                    s.pop(i)
                    return True
            return False

        while True:
            if not removeChar('A'):
                return False
            if not removeChar('B'):
                return True

        return False

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Greedy + Two Pointers

Intuition

The key insight is that each player's moves are independent. Removing an 'A' from a sequence of A's doesn't affect Bob's sequences of B's, and vice versa. So instead of simulating the game, we can count how many moves each player has available. For a run of consecutive same-colored pieces of length k, a player can remove k - 2 pieces (since they need neighbors on both sides). Alice wins if she has more moves than Bob.

Algorithm

Use two pointers to track consecutive runs of the same color.
For each position, calculate how many "extra" pieces exist beyond the first two in the current run.
Add these extras to Alice's count if the color is 'A', or Bob's count if 'B'.
Return true if Alice has more moves than Bob.

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        alice = bob = l = 0

        for r in range(len(colors)):
            if colors[l] != colors[r]:
                l = r

            extra = r - l - 1
            if extra > 0:
                if colors[l] == 'A':
                    alice += 1
                else:
                    bob += 1

        return alice > bob

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

3. Greedy

Intuition

This is a cleaner way to count available moves. For each position in the middle of the string, we check if it forms a "triplet" of same-colored pieces. Each such triplet represents one potential move for that player. Since removing a piece from a longer run still leaves valid triplets, we simply count all triplet centers for each player.

Algorithm

Initialize counters for Alice and Bob.
Iterate through positions 1 to n-2 (excluding endpoints).
At each position, check if the current piece matches both its neighbors.
If so, increment Alice's counter for 'A' or Bob's counter for 'B'.
Return true if Alice's count exceeds Bob's count.

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        alice, bob = 0, 0

        for i in range(1, len(colors) - 1):
            if colors[i - 1] == colors[i] == colors[i + 1]:
                if colors[i] == 'A':
                    alice += 1
                if colors[i] == 'B':
                    bob += 1

        return alice > bob

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Simulating the Game Turn by Turn

A common mistake is to simulate the actual game by removing pieces one at a time and alternating turns. This leads to O(n^2) time complexity because each removal requires scanning and modifying the string. The key insight is that removing an 'A' from a sequence of A's doesn't affect Bob's available moves on B sequences, and vice versa. Instead of simulating, simply count the available moves for each player upfront.

Miscounting Available Moves

When counting moves, remember that a player can only remove a piece if it has neighbors of the same color on both sides. For a run of k consecutive same-colored pieces, the number of removable pieces is k - 2 (not k or k - 1). A run of length 1 or 2 gives zero moves. Some solutions incorrectly count individual pieces or forget to subtract 2 for the boundary pieces that cannot be removed.

Using the Wrong Win Condition

The problem asks if Alice wins, and Alice moves first. Some solutions return alice >= bob instead of alice > bob. Since Alice needs strictly more moves than Bob to win (she goes first, so if they have equal moves, Bob makes the last move and Alice loses), the correct condition is alice > bob.