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.
One way to solve this question is to count the number of removable sequences for both Alice and Bob. A removable sequence is an occurrence of three consecutive 'A's for Alice and three consecutive 'B's for Bob. The player who has more removable sequences controls the pace of the game and can potentially use up all the opponent's moves.
This C solution iterates through the string, counting the possible moves for Alice ('AAA') and Bob ('BBB'). It uses a simple for loop, and the counts are compared to decide if Alice wins or not.
Time complexity is O(n), where n is the length of the string. Space complexity is O(1) as we use a fixed amount of space.
This approach involves using dynamic programming to determine the possible count of removable pieces for Alice and Bob. By maintaining an array, we can track the available moves dynamically, updating counts as pieces get removed, until no further moves are left for one player. This is more complex than the counting method but can offer deeper insight into game states.
This C solution uses dynamic programming to precompute possible moves for both Alice and Bob by filling arrays dp_a and dp_b. The arrays store cumulative possible moves at each step.
Time complexity is O(n) with space complexity of O(n) due to the arrays.
We count the number of times that the string colors contains three consecutive 'A's or three consecutive 'B's, denoted as a and b, respectively.
Finally, we check whether a is greater than b. If it is, we return true. Otherwise, we return false.
The time complexity is O(n), where n is the length of the string colors. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Count Removable Sequences | Time complexity is O(n), where n is the length of the string. Space complexity is O(1) as we use a fixed amount of space. |
| Dynamic Programming Approach | Time complexity is O(n) with space complexity of O(n) due to the arrays. |
| Counting | — |
| 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 |
Remove Colored Pieces if Both Neighbors are the Same Color - Leetcode 2038 - Python • NeetCodeIO • 10,421 views views
Watch 9 more video solutions →Practice Remove Colored Pieces if Both Neighbors are the Same Color with our built-in code editor and test cases.
Practice on FleetCode