Watch 10 video solutions for Remove Colored Pieces if Both Neighbors are the Same Color, a medium level problem involving Math, String, Greedy. This walkthrough by NeetCodeIO has 10,421 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
'A' if both its neighbors are also colored 'A'. She is not allowed to remove pieces that are colored 'B'.'B' if both its neighbors are also colored 'B'. He is not allowed to remove pieces that are colored 'A'.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 <= 105colors consists of only the letters 'A' and 'B'Problem Overview: You are given a string of characters A and B. Alice can remove an A piece only if both neighbors are also A, while Bob can remove a B piece only if both neighbors are B. Players alternate turns with Alice starting first. The task is to determine whether Alice wins assuming both players play optimally.
Approach 1: Count Removable Sequences (Greedy) (Time: O(n), Space: O(1))
The key observation: a player can only remove pieces from runs of their own color that have length ≥ 3. For a contiguous block of length k, the number of valid removals is k - 2. Scan the string once and track consecutive segments of A and B. For each segment, add k - 2 to Alice's move count if it is an A segment, or to Bob's move count if it is a B segment. After processing the entire string, compare total possible moves. If Alice has strictly more possible removals than Bob, she wins; otherwise Bob wins. This works because removals inside a segment never create new opportunities for the opponent. The strategy relies on greedy counting of independent segments and uses concepts from greedy reasoning on a string.
Approach 2: Dynamic Programming Approach (Time: O(n), Space: O(n))
A dynamic programming perspective models each contiguous segment as a small game. Let dp[i] represent the maximum removable pieces within a run ending at index i. When the current character matches the previous one, extend the run and update the potential moves using the recurrence based on the current run length. Every time a run length becomes at least 3, a new removable move appears. Summing these values across runs gives the same move counts for Alice and Bob as the greedy method. This formulation highlights the underlying game theory structure: each segment behaves like an independent subgame where moves reduce the segment length by one. Although DP is not required for optimal performance, it makes the incremental state transitions explicit.
Recommended for interviews: The greedy run-count approach is what interviewers expect. It shows you recognize the invariant that only runs of length ≥3 matter and that each run contributes k - 2 independent moves. Mentioning the DP viewpoint demonstrates deeper understanding of the game's structure, but implementing the O(n) greedy scan is the clearest and most efficient solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Removable Sequences (Greedy) | O(n) | O(1) | Best general solution; simple single pass counting of runs |
| Dynamic Programming on Runs | O(n) | O(n) | Useful when demonstrating game-state transitions or extending to similar problems |