# Remove Colored Pieces if Both Neighbors are the Same Color
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color)
Canonical: https://scaleengineer.com/dsa/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Data structures:** String
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Roblox](https://scaleengineer.com/companies/roblox), [Yelp](https://scaleengineer.com/companies/yelp), [MathWorks](https://scaleengineer.com/companies/mathworks), [Unity](https://scaleengineer.com/companies/unity)
---
## Problem
There are `n` pieces arranged in a line, and each piece is colored either by `'A'` or by `'B'`. You are given a string `colors` of length `n` where `colors[i]` is the color of the `ith` piece.

Alice and Bob are playing a game where they take **alternating turns** removing pieces from the line. In this game, Alice moves **first**.

* Alice is only allowed to remove a piece colored `'A'` if **both its neighbors** are also colored `'A'`. She is **not allowed** to remove pieces that are colored `'B'`.
* Bob is only allowed to remove a piece colored `'B'` if **both its neighbors** are also colored `'B'`. He is **not allowed** to remove pieces that are colored `'A'`.
* Alice and Bob **cannot** remove pieces from the edge of the line.
* If a player cannot make a move on their turn, that player **loses** and the other player **wins**.

Assuming Alice and Bob play optimally, return `true` _if Alice wins, or return_ `false` _if Bob wins_.

**Example 1:**

**Input:** colors = "AAABABB"
**Output:** true
**Explanation:**
AAABABB -> AABABB
Alice moves first.
She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.

Now it's Bob's turn.
Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
Thus, Alice wins, so return true.

**Example 2:**

**Input:** colors = "AA"
**Output:** false
**Explanation:**
Alice has her turn first.
There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
Thus, Bob wins, so return false.

**Example 3:**

**Input:** colors = "ABBBBBBBAAA"
**Output:** false
**Explanation:**
ABBBBBBBAAA -> ABBBBBBBAA
Alice moves first.
Her only option is to remove the second to last 'A' from the right.

ABBBBBBBAA -> ABBBBBBAA
Next is Bob's turn.
He has many options for which 'B' piece to remove. He can pick any.

On Alice's second turn, she has no more pieces that she can remove.
Thus, Bob wins, so return false.

**Constraints:**

* `1 <= colors.length <= 105`
* `colors` consists of only the letters `'A'` and `'B'`

# Approaches
## Recursive Minimax with Memoization
This approach models the game as a classic turn-based game, using a recursive function with memoization (a form of dynamic programming) to explore the game tree. It determines if Alice has a winning strategy by checking all possible move sequences. This is a standard way to solve impartial games but is too slow for the constraints of this problem.
**Time:** O(S * N^2), where S is the number of reachable game states and N is the string length. Each state transition involves iterating through the string (O(N)) and creating a substring (O(N)), leading to O(N^2) work per state. The number of states S can be very large. · **Space:** O(S * N), where S is the number of reachable game states and N is the length of the string. This is prohibitively large.
**Pros:** Correctly models the turn-based nature of the game.; It is a general approach that can be adapted to other, more complex impartial games.
**Cons:** Extremely inefficient and will result in a Time Limit Exceeded (TLE) error for the given constraints.; High time complexity due to the large state space and expensive string operations.; High space complexity to store the memoization table.; Overly complex for this problem, as it fails to recognize the game's simpler underlying structure.
### Explanation
This method involves a full simulation of the game using a recursive minimax algorithm. We define a function that determines if the current player to move can win from a given board state (`colors` string). Since the same game state can be reached via different move sequences, we use a hash map for memoization to cache the results of subproblems, avoiding redundant computations.

For the current player (e.g., Alice), the function iterates through all her possible moves. A move is valid if she can find a piece 'A' surrounded by two other 'A's. For each valid move, she simulates removing the piece and recursively calls the function for the opponent's turn on the new board state. If any of these simulated paths lead to a state where the opponent is guaranteed to lose, then the current move is a winning one, and Alice can win. If all her possible moves lead to states where the opponent can win, then Alice cannot force a win from her current position.

This approach is correct in theory but impractical due to the massive number of possible game states and the high cost of string manipulations (creating a new string for each move) in each recursive call.

```java
// This conceptual implementation is too slow and will TLE.
class Solution {
    private java.util.Map<String, Boolean> memo = new java.util.HashMap<>();

    public boolean winnerOfGame(String colors) {
        return canCurrentPlayerWin(colors, true);
    }

    private boolean canCurrentPlayerWin(String colors, boolean isAliceTurn) {
        String key = colors + (isAliceTurn ? 'A' : 'B');
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        char playerChar = isAliceTurn ? 'A' : 'B';
        boolean canMove = false;
        for (int i = 1; i < colors.length() - 1; i++) {
            if (colors.charAt(i - 1) == playerChar && colors.charAt(i) == playerChar && colors.charAt(i + 1) == playerChar) {
                canMove = true;
                String nextState = colors.substring(0, i) + colors.substring(i + 1);
                // If the other player CANNOT win from the next state, the current player wins.
                if (!canCurrentPlayerWin(nextState, !isAliceTurn)) {
                    memo.put(key, true);
                    return true;
                }
            }
        }

        // If the current player cannot make a move, or all moves lead to the other player winning,
        // the current player loses.
        memo.put(key, false);
        return false;
    }
}
```
### Algorithm
- Define a recursive function, say `canCurrentPlayerWin(colors, isAliceTurn)`, which returns `true` if the current player can force a win from the given state.
- Use a `Map` for memoization to store results for states `(colors, isAliceTurn)` that have already been computed.
- **Base Case**: If the current player has no valid moves, they lose. Return `false`.
- **Recursive Step**: 
  - Iterate through all possible moves for the current player (`'A'` for Alice, `'B'` for Bob).
  - For each move, generate the `nextState` string by removing the piece.
  - Make a recursive call `canCurrentPlayerWin(nextState, !isAliceTurn)` to see if the *other* player can win from the `nextState`.
  - If this recursive call returns `false` (meaning the other player loses), it means the current move is a winning move. The current player can win, so we memoize and return `true`.
- If the loop finishes and no winning move is found, it means the current player loses from this state. Memoize and return `false`.
- The initial call is `canCurrentPlayerWin(initial_colors, true)`.

## Single Pass Counting
This optimal approach is based on the critical observation that moves made by Alice do not create or remove opportunities for Bob, and vice-versa. The game is not about strategic blocking but about which player has more available moves. The winner is simply the player who starts with more potential moves. The solution is to count the total number of possible moves for each player from the initial configuration and compare them.
**Time:** O(N), where N is the length of the string `colors`. We iterate through the string only once. · **Space:** O(1), as we only use a few integer variables for counters, regardless of the input string's size.
**Pros:** Highly efficient, with a linear time complexity.; Uses constant extra space.; Simple and straightforward to implement once the core logic is understood.
**Cons:** The approach relies on a key insight that might not be immediately obvious. The reasoning that the moves are independent is crucial.
### Explanation
The key insight for this problem is that the set of moves available to Alice (removing an 'A' from an 'AAA' sequence) and the set of moves available to Bob (removing a 'B' from a 'BBB' sequence) are completely independent. When Alice removes an 'A', the string shortens, but it can never create a new 'BBB' sequence for Bob. Similarly, Bob's moves don't create 'AAA' sequences for Alice. 

This means the game is not strategic in the typical sense. It's a simple race. The total number of moves each player can make throughout the game is fixed from the start. Alice wins if and only if she has more moves available to her than Bob has. If Alice has `k` moves and Bob has `m` moves, Alice moves on turns 1, 3, 5, ... and Bob on 2, 4, 6, ... . If `k > m`, Alice will be able to make her `(m+1)`-th move, at which point Bob will have no moves left and will lose.

Therefore, the problem reduces to counting the number of 'AAA' substrings and 'BBB' substrings. We can do this in a single pass through the string.

```java
class Solution {
    public boolean winnerOfGame(String colors) {
        int aliceMoves = 0;
        int bobMoves = 0;
        int n = colors.length();

        // No moves are possible if the string has fewer than 3 characters.
        // Alice moves first and cannot move, so she loses.
        if (n < 3) {
            return false;
        }

        // We only need to check for removable pieces, which are not on the edges.
        for (int i = 1; i < n - 1; i++) {
            char prev = colors.charAt(i - 1);
            char curr = colors.charAt(i);
            char next = colors.charAt(i + 1);

            if (prev == 'A' && curr == 'A' && next == 'A') {
                aliceMoves++;
            } else if (prev == 'B' && curr == 'B' && next == 'B') {
                bobMoves++;
            }
        }

        // Alice wins if she has strictly more moves than Bob.
        return aliceMoves > bobMoves;
    }
}
```
### Algorithm
- Initialize two integer counters, `aliceMoves` and `bobMoves`, to zero.
- Iterate through the input string `colors` from the second character to the second-to-last character (from index 1 to `n-2`).
- At each index `i`, check the triplet of characters `colors[i-1]`, `colors[i]`, `colors[i+1]`.
- If the triplet is `'A', 'A', 'A'`, increment `aliceMoves`.
- If the triplet is `'B', 'B', 'B'`, increment `bobMoves`.
- After the loop completes, compare the two counters.
- Return `true` if `aliceMoves > bobMoves`, otherwise return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean winnerOfGame(String colors) {
    int n = colors.length();
    int a = 0, b = 0;
    for (int i = 0, j = 0; i < n; i = j) {
      while (j < n && colors.charAt(j) == colors.charAt(i)) {
        ++j;
      }
      int m = j - i - 2;
      if (m > 0) {
        if (colors.charAt(i) == 'A') {
          a += m;
        } else {
          b += m;
        }
      }
    }
    return a > b;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool winnerOfGame(string colors) {
    int n = colors.size();
    int a = 0, b = 0;
    for (int i = 0, j = 0; i < n; i = j) {
      while (j < n && colors[j] == colors[i]) {
        ++j;
      }
      int m = j - i - 2;
      if (m > 0) {
        if (colors[i] == 'A') {
          a += m;
        } else {
          b += m;
        }
      }
    }
    return a > b;
  }
};

```

### Python

```python
class Solution:
    def winnerOfGame(self, colors: str) -> bool: a = b = 0 for c, v in groupby(colors): m = len(list(v)) - 2 if m > 0 and c == 'A': a += m elif m > 0 and c == 'B': b += m return a > b

```