Skip to main content
Talentd

Remove Colored Pieces if Both Neighbors are the Same Color - Solution & Explanation

MediumMathStringGreedyGame Theory14 min readAsked at: Mathworks, Unity, Yelp
Practice this problem

Problem Statement

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.

  • Alice is only allowed to remove a piece colored 'A' if both its neighbors are also colored 'A'. She is not allowed to remove pieces that are colored 'B'.
  • Bob is only allowed to remove a piece colored 'B' if both its neighbors are also colored 'B'. He is not allowed to remove pieces that are colored 'A'.
  • Alice and Bob cannot remove pieces from the edge of the line.
  • If a player cannot make a move on their turn, that player loses and the other player wins.

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 <= 105
  • colors consists of only the letters 'A' and 'B'

Approach Overview

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 1: Count Removable Sequences

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(n) with space complexity of O(n) due to the arrays.

Try this approach in the editor →

Approach 3: Counting

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Count Removable Sequences (Greedy)O(n)O(1)Best general solution; simple single pass counting of runs
Dynamic Programming on RunsO(n)O(n)Useful when demonstrating game-state transitions or extending to similar problems

Video Solution

Remove Colored Pieces if Both Neighbors are the Same Color - Leetcode 2038 - Python • NeetCodeIO • 10,512 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Remove Colored Pieces if Both Neighbors are the Same Color easy or hard?
The problem is classified as Medium on LeetCode. The challenge is recognizing that the game does not require simulation of turns. Once you realize each run contributes k−2 moves independently, the solution becomes a straightforward linear scan.
Remove Colored Pieces if Both Neighbors are the Same Color Python/Java solution
In Python or Java, iterate through the string while counting consecutive characters. When the run length of 'A' exceeds two, increment Alice's move counter; do the same for 'B' and Bob. After the loop, return whether AliceMoves > BobMoves. This implementation runs in O(n) time with constant extra space.
How to solve Remove Colored Pieces if Both Neighbors are the Same Color in O(n)?
Iterate through the string and track the length of each contiguous run of identical characters. Whenever a run length reaches k, it contributes k−2 possible removals. Add these moves to Alice if the run is A, or to Bob if the run is B. After processing the entire string, compare the totals to determine the winner.
What is the best approach for Remove Colored Pieces if Both Neighbors are the Same Color?
The optimal approach is a greedy run-count strategy. Scan the string and count consecutive segments of A and B. For a segment of length k, the number of removable moves is k−2. Sum the possible moves for Alice and Bob separately; Alice wins if her total moves exceed Bob's. This runs in O(n) time and O(1) space.
Is Remove Colored Pieces if Both Neighbors are the Same Color asked at Google/Amazon/Meta?
This problem appears in interview preparation sets for companies that evaluate greedy reasoning and simple game theory logic. Variants of the problem have been discussed in interviews at large tech companies where candidates must reason about optimal moves and invariants in turn-based games.
What data structure is used in Remove Colored Pieces if Both Neighbors are the Same Color?
The solution primarily uses string traversal and counters. No complex data structures are needed. The algorithm relies on tracking run lengths within the string and applying a greedy counting rule to determine how many moves each player can make.
What is the time complexity of Remove Colored Pieces if Both Neighbors are the Same Color?
The optimal greedy solution runs in O(n) time because the string is scanned once to count consecutive runs. Space complexity is O(1) since only counters for Alice's and Bob's moves are stored. No additional data structures are required.

Ready to solve this problem?

Practice Remove Colored Pieces if Both Neighbors are the Same Color with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Subarray With Maximum Bitwise AND