⚡Flashcard Drill➔
NeetCode #805LC-2038MediumGreedy
← Back to All Problems

#805 · #2038 · Remove Colored Pieces if Both Neighbors are the Same Color(如果相邻两个颜色均相同则删除当前颜色)

📌 Problem Statement & Constraints

There is a row of pieces coloured A or B. Alice and Bob take turns (Alice first); a player removes one of their own pieces that has both neighbours the same colour. The player who cannot move loses. Return true if Alice wins. Constraints: 1 <= colors.length <= 10^5, colors[i] is A or B.

💡 Core Algorithmic Approaches

  1. Within a maximal run of a colour of length L, the available moves are max(0, L - 2), since a piece needs two same-coloured neighbours.
  2. The two players never interfere: removing a piece only shortens runs of its own colour.
  3. So count Alice's total available moves and Bob's total available moves.
  4. Alice wins iff her move count is strictly greater than Bob's, since Alice moves first and moves alternate.

💻 Benchmark Python3 Implementation

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass over interior positions.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Counting runs instead of removable pieces: a run of length L contributes L - 2 moves, not 1.
  • Using a >= b: Alice needs strictly more moves, because if counts are equal the alternating play exhausts Alice first.
  • Iterating over the whole string: the first and last pieces have no two neighbours, so the loop runs 1..n-2.
  • Simulating the game: the move-count argument makes simulation unnecessary.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems