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
- Within a maximal run of a colour of length
L, the available moves aremax(0, L - 2), since a piece needs two same-coloured neighbours. - The two players never interfere: removing a piece only shortens runs of its own colour.
- So count Alice's total available moves and Bob's total available moves.
- 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
LcontributesL - 2moves, 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.