Remove Colored Pieces if Both Neighbors are the Same Color

How it works

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.

Steps

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

Complexity

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

Things to watch for

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.

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

class Solution {
public:
    bool winnerOfGame(string colors) {
        int alice = 0, bob = 0;

        for (int i = 1; i < colors.size() - 1; i++) {
            if (colors[i - 1] == colors[i] && colors[i] == colors[i + 1]) {
                if (colors[i] == 'A') {
                    alice++;
                }
                if (colors[i] == 'B') {
                    bob++;
                }
            }
        }

        return alice > bob;
    }
};