Remove Colored Pieces Same Color Solution

Q: 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.

Q: 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.

The problem

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 i^th 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 <= 10⁵
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.

Python

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        a_moves = b_moves = 0
        n = len(colors)
        for i in range(1, n - 1):
            if colors[i - 1] == 'A' == colors[i] == colors[i + 1]:
                a_moves += 1
            if colors[i - 1] == 'B' == colors[i] == colors[i + 1]:
                b_moves += 1
        return a_moves > b_moves

Java

public class Solution {
    public boolean winnerOfGame(String colors) {
        int a_moves = 0, b_moves = 0;
        int n = colors.length();
        for (int i = 1; i < n - 1; i++) {
            if (colors.charAt(i - 1) == 'A' && colors.charAt(i) == 'A' && colors.charAt(i + 1) == 'A') {
                a_moves++;
            }
            if (colors.charAt(i - 1) == 'B' && colors.charAt(i) == 'B' && colors.charAt(i + 1) == 'B') {
                b_moves++;
            }
        }
        return a_moves > b_moves;
    }
}

C++

#include <string>
using namespace std;

class Solution {
public:
    bool winnerOfGame(string colors) {
        int a_moves = 0, b_moves = 0;
        int n = colors.size();
        for (int i = 1; i < n - 1; i++) {
            if (colors[i - 1] == 'A' && colors[i] == 'A' && colors[i + 1] == 'A') {
                a_moves++;
            }
            if (colors[i - 1] == 'B' && colors[i] == 'B' && colors[i + 1] == 'B') {
                b_moves++;
            }
        }
        return a_moves > b_moves;
    }
};

JavaScript

var winnerOfGame = function(colors) {
    let a_moves = 0, b_moves = 0;
    let n = colors.length;
    for (let i = 1; i < n - 1; i++) {
        if (colors[i - 1] === 'A' && colors[i] === 'A' && colors[i + 1] === 'A') {
            a_moves++;
        }
        if (colors[i - 1] === 'B' && colors[i] === 'B' && colors[i + 1] === 'B') {
            b_moves++;
        }
    }
    return a_moves > b_moves;
};

#include <stdbool.h>
#include <string.h>

bool winnerOfGame(char *colors) {
    int a_moves = 0, b_moves = 0;
    int n = strlen(colors);
    for (int i = 1; i < n - 1; i++) {
        if (colors[i - 1] == 'A' && colors[i] == 'A' && colors[i + 1] == 'A') {
            a_moves++;
        }
        if (colors[i - 1] == 'B' && colors[i] == 'B' && colors[i + 1] == 'B') {
            b_moves++;
        }
    }
    return a_moves > b_moves;
}

public class Solution {
    public bool WinnerOfGame(string colors) {
        int a_moves = 0, b_moves = 0;
        int n = colors.Length;
        for (int i = 1; i < n - 1; i++) {
            if (colors[i - 1] == 'A' && colors[i] == 'A' && colors[i + 1] == 'A') {
                a_moves++;
            }
            if (colors[i - 1] == 'B' && colors[i] == 'B' && colors[i + 1] == 'B') {
                b_moves++;
            }
        }
        return a_moves > b_moves;
    }
}

The Python implementation similarly iterates over the input string, counting 'AAA' and 'BBB' sequences. This count directly determines whether Alice has a winning strategy.

Complexity

Time complexity is O(n), and space complexity is O(1).

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.

Python

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        n = len(colors)
        dp_a = [0] * n
        dp_b = [0] * n
        for i in range(1, n - 1):
            if colors[i] == 'A':
                dp_a[i] = dp_a[i - 1] + (1 if colors[i - 1] == 'A' and colors[i + 1] == 'A' else 0)
            elif colors[i] == 'B':
                dp_b[i] = dp_b[i - 1] + (1 if colors[i - 1] == 'B' and colors[i + 1] == 'B' else 0)
        return dp_a[-2] > dp_b[-2]

Java

public class Solution {
    public boolean winnerOfGame(String colors) {
        int n = colors.length();
        int[] dp_a = new int[n];
        int[] dp_b = new int[n];
        for (int i = 1; i < n - 1; i++) {
            if (colors.charAt(i) == 'A') {
                dp_a[i] = dp_a[i - 1] + (colors.charAt(i - 1) == 'A' && colors.charAt(i + 1) == 'A' ? 1 : 0);
            } else if (colors.charAt(i) == 'B') {
                dp_b[i] = dp_b[i - 1] + (colors.charAt(i - 1) == 'B' && colors.charAt(i + 1) == 'B' ? 1 : 0);
            }
        }
        return dp_a[n - 2] > dp_b[n - 2];
    }
}

C++

#include <vector>
using namespace std;

class Solution {
public:
    bool winnerOfGame(string colors) {
        int n = colors.size();
        vector<int> dp_a(n, 0), dp_b(n, 0);
        for (int i = 1; i < n - 1; i++) {
            if (colors[i] == 'A') {
                dp_a[i] = dp_a[i - 1] + (colors[i - 1] == 'A' && colors[i + 1] == 'A');
            } else if (colors[i] == 'B') {
                dp_b[i] = dp_b[i - 1] + (colors[i - 1] == 'B' && colors[i + 1] == 'B');
            }
        }
        return dp_a[n - 2] > dp_b[n - 2];
    }
};

JavaScript

var winnerOfGame = function(colors) {
    let n = colors.length;
    let dp_a = new Array(n).fill(0);
    let dp_b = new Array(n).fill(0);
    for (let i = 1; i < n - 1; i++) {
        if (colors[i] === 'A') {
            dp_a[i] = dp_a[i - 1] + (colors[i - 1] === 'A' && colors[i + 1] === 'A' ? 1 : 0);
        } else if (colors[i] === 'B') {
            dp_b[i] = dp_b[i - 1] + (colors[i - 1] === 'B' && colors[i + 1] === 'B' ? 1 : 0);
        }
    }
    return dp_a[n - 2] > dp_b[n - 2];
};

#include <stdbool.h>
#include <string.h>

bool winnerOfGame(char *colors) {
    int n = strlen(colors);
    int dp_a[n], dp_b[n];
    for (int i = 0; i < n; i++) {
        dp_a[i] = dp_b[i] = 0;
    }
    for (int i = 1; i < n - 1; i++) {
        if (colors[i] == 'A') {
            dp_a[i] = dp_a[i - 1] + (colors[i - 1] == 'A' && colors[i + 1] == 'A');
        } else if (colors[i] == 'B') {
            dp_b[i] = dp_b[i - 1] + (colors[i - 1] == 'B' && colors[i + 1] == 'B');
        }
    }
    return dp_a[n - 2] > dp_b[n - 2];
}

public class Solution {
    public bool WinnerOfGame(string colors) {
        int n = colors.Length;
        int[] dp_a = new int[n];
        int[] dp_b = new int[n];
        for (int i = 1; i < n - 1; i++) {
            if (colors[i] == 'A') {
                dp_a[i] = dp_a[i - 1] + (colors[i - 1] == 'A' && colors[i + 1] == 'A' ? 1 : 0);
            } else if (colors[i] == 'B') {
                dp_b[i] = dp_b[i - 1] + (colors[i - 1] == 'B' && colors[i + 1] == 'B' ? 1 : 0);
            }
        }
        return dp_a[n - 2] > dp_b[n - 2];
    }
}

Python employs a similar strategy using lists to account for each player's possible moves, providing a comprehensive approach to track game state changes.

Complexity

Time complexity is O(n), and space complexity is O(n) due to list initialization.

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

TypeScript

function winnerOfGame(colors: string): boolean {
    const n = colors.length;
    let [a, b] = [0, 0];
    for (let i = 0, j = 0; i < n; i = j) {
        while (j < n && colors[j] === colors[i]) {
            ++j;
        }
        const m = j - i - 2;
        if (m > 0) {
            if (colors[i] === 'A') {
                a += m;
            } else {
                b += m;
            }
        }
    }
    return a > b;
}

func winnerOfGame(colors string) bool {
	n := len(colors)
	a, b := 0, 0
	for i, j := 0, 0; i < n; i = j {
		for j < n && colors[j] == colors[i] {
			j++
		}
		m := j - i - 2
		if m > 0 {
			if colors[i] == 'A' {
				a += m
			} else {
				b += m
			}
		}
	}
	return a > b
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Count Removable Sequences	Time complexity is O(n), and space complexity is O(1).
Dynamic Programming Approach	Time complexity is O(n), and space complexity is O(n) due to list initialization.
Counting	–

Complexity analysis

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

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.

Remove Colored Pieces if Both Neighbors are the Same Color solution and explanation

The problem

Approach overview

Approach 1: Count Removable Sequences

Approach 2: Dynamic Programming Approach

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Remove Colored Pieces if Both Neighbors are the Same Color solution and explanation

The problem

Approach overview

Approach 1: Count Removable Sequences

Approach 2: Dynamic Programming Approach

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems