Remove Colored Pieces if Both Neighbors are the Same Color

medium math string greedy game theory

Problem

Alice and Bob alternate turns. Alice can remove an 'A' whose both neighbors are 'A'; Bob does the same with 'B'. Alice moves first; the loser is the first one unable to move. Return true if Alice wins.

Inputcolors = "AAABABB"

Outputtrue

Alice has 1 AAA center, Bob has 0 BBB centers — Alice wins.

colors (A/B string)

def winner_of_game(colors):
    a = b = 0
    for i in range(1, len(colors) - 1):
        if colors[i - 1] == colors[i] == colors[i + 1]:
            if colors[i] == 'A':
                a += 1
            else:
                b += 1
    return a > b

function winnerOfGame(colors) {
  let a = 0, b = 0;
  for (let i = 1; i < colors.length - 1; i++) {
    if (colors[i - 1] === colors[i] && colors[i] === colors[i + 1]) {
      if (colors[i] === 'A') a++;
      else b++;
    }
  }
  return a > b;
}

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

bool winnerOfGame(string colors) {
    int a = 0, b = 0;
    for (int i = 1; i + 1 < (int)colors.size(); i++) {
        if (colors[i-1] == colors[i] && colors[i] == colors[i+1]) {
            if (colors[i] == 'A') a++;
            else b++;
        }
    }
    return a > b;
}

Explanation

The whole game collapses to simple counting once you notice that a player's moves don't interfere with the opponent's. Alice can only remove an A that sits between two other As (an AAA center), and doing so never creates or destroys any BBB center for Bob, and vice versa.

That means the number of moves each player ever gets is fixed from the start. Alice's total moves equal the count of AAA centers, and Bob's equal the count of BBB centers.

So we slide a 3-wide window across the string. For each middle position i we check if colors[i-1], colors[i], and colors[i+1] are all the same; if so we add 1 to a (for A) or b (for B).

Since the players alternate and Alice goes first, Alice wins exactly when she has strictly more moves: a > b.

Example: colors = "AAABABB". There is one AAA center (at index 1) and no BBB center, so a = 1, b = 0, and 1 > 0 → Alice wins (true).

Time: O(n) Space: O(1)