{x}
blog image

Remove Colored Pieces if Both Neighbors are the Same Color

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'

Solution Explanation for LeetCode 2038: Remove Colored Pieces if Both Neighbors are the Same Color

This problem involves a two-player game where players take turns removing pieces from a line of colored pieces ('A' or 'B'). The winning condition is based on whether a player can make a move. The core strategy is to count the potential moves for each player and determine who has more.

Approach: Greedy Counting

Instead of simulating the entire game, we can use a greedy approach. We observe that the outcome of the game depends solely on the number of removable pieces for each player. The player with more removable pieces is more likely to win. Therefore, we count the number of removable 'A' pieces for Alice and the number of removable 'B' pieces for Bob.

The key insight is that a piece can only be removed if it has two identical neighbors. This means we need to find consecutive sequences of at least three 'A's or three 'B's. For each such sequence of length k, there are k - 2 removable pieces. We simply count these removable pieces for Alice and Bob, and compare them to determine the winner.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the colors string. We iterate through the string once to count the removable pieces.
  • Space Complexity: O(1). We only use a constant amount of extra space to store the counts of removable 'A' and 'B' pieces.

Code Implementation in Multiple Languages

The following code implements the greedy counting approach:

Python3

from itertools import groupby
 
class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        a_count = 0
        b_count = 0
        for char, group in groupby(colors):
            length = len(list(group))
            if length >= 3:
                if char == 'A':
                    a_count += length - 2
                else:
                    b_count += length - 2
        return a_count > b_count

Java

class Solution {
    public boolean winnerOfGame(String colors) {
        int aCount = 0;
        int bCount = 0;
        char prev = ' ';
        int count = 0;
        for (char c : colors.toCharArray()) {
            if (c == prev) {
                count++;
            } else {
                if (count >= 3) {
                    if (prev == 'A') aCount += count - 2;
                    else bCount += count - 2;
                }
                prev = c;
                count = 1;
            }
        }
        if (count >= 3) {
            if (prev == 'A') aCount += count - 2;
            else bCount += count - 2;
        }
        return aCount > bCount;
    }
}

C++

#include <string>
#include <algorithm>
 
using namespace std;
 
class Solution {
public:
    bool winnerOfGame(string colors) {
        int a_count = 0;
        int b_count = 0;
        char prev = ' ';
        int count = 0;
        for (char c : colors) {
            if (c == prev) {
                count++;
            } else {
                if (count >= 3) {
                    if (prev == 'A') a_count += count - 2;
                    else b_count += count - 2;
                }
                prev = c;
                count = 1;
            }
        }
        if (count >= 3) {
            if (prev == 'A') a_count += count - 2;
            else b_count += count - 2;
        }
        return a_count > b_count;
    }
};

Javascript

/**
 * @param {string} colors
 * @return {boolean}
 */
var winnerOfGame = function(colors) {
    let aCount = 0;
    let bCount = 0;
    let prev = ' ';
    let count = 0;
    for (let i = 0; i < colors.length; i++) {
        const c = colors[i];
        if (c === prev) {
            count++;
        } else {
            if (count >= 3) {
                if (prev === 'A') aCount += count - 2;
                else bCount += count - 2;
            }
            prev = c;
            count = 1;
        }
    }
    if (count >= 3) {
        if (prev === 'A') aCount += count - 2;
        else bCount += count - 2;
    }
    return aCount > bCount;
};

These solutions all follow the same basic algorithm, differing only in their syntax and specific library functions used. They all achieve the optimal time and space complexity described above.