Vultr DocsLatest Content

Remove Colored Pieces if Both Neighbors are the Same Color

Updated on 20 June, 2025
Remove Colored Pieces if Both Neighbors are the Same Color header image

Problem Statement

In this problem, there are n pieces lined up. Each piece is labeled either with an 'A' or a 'B'. These labels are represented in a string called colors, where the character colors[i] tells the color of the i-th piece.

Alice and Bob engage in a strategy game involving these pieces. The game follows these rules:

  • The game is played turn by turn with Alice always starting.
  • Alice can only remove an 'A' piece provided it is surrounded on both sides by other 'A' pieces.
  • Bob follows a similar rule for 'B' pieces; he can only remove a 'B' piece if it is flanked by 'B' pieces on both sides.
  • Neither player can remove pieces located at the boundaries of the string.
  • The game ends when a player cannot make a move, making them the loser.

Given these rules, the task is to predict whether Alice will win the game if both players play optimally. Return true if Alice wins, otherwise false.

Examples

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 and Intuition

The outcome of this game heavily relies on the initial configuration of the colors string and the strategy both players follow. Here is a step-by-step approach based on the rules:

  1. Scan the string colors initially and count contiguous segments of 'A's and 'B's.
  2. For a segment of 'A's or 'B's to be actionable by either player, it must consist of at least 3 same colored pieces in a row. This is because a piece can only be removed when both its neighbors are of the same type.
  3. Alice's strategy will be to remove 'A' pieces such that the largest segments of 'A's are broken down, hindering Bob's chance to form actionable segments of 'B's and vice versa for Bob.
  4. Both players continue to take turns removing pieces (when possible) until one player cannot make a move. The player unable to make a move loses the game.
  5. Implementing this strategy in simulation or through clever counting might yield the expected winner.

Considering these steps can provide an efficient approach to determining the winner in this strategic game, based on the starting setup of the string colors.

The examples given illustrate different scenarios:

  • In the first case, Alice quickly wins as her actions directly result in Bob having no moves left.
  • In the second example, Alice has no move initially, leading to her immediate loss.
  • In the third scenario, although Alice has moves initially, the sheer number of 'B's gives Bob the advantage, allowing him to win eventually when Alice runs out of moves.

These examples hint towards evaluating the number of possible moves and the structure of the initial string to determine the winning strategy.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    bool winnerOfGame(string sequence) {
        int aliceCount = 0;
        int bobCount = 0;
        
        for (int i = 1; i < sequence.length() - 1; i++) {
            if (sequence[i - 1] == sequence[i] && sequence[i] == sequence[i + 1]) {
                if (sequence[i] == 'A') {
                    aliceCount++;
                } else {
                    bobCount++;
                }
            }
        }
        
        return aliceCount > bobCount;
    }
};

The problem involves determining the winner in a game where players "Alice" and "Bob" remove pieces from a sequence under certain conditions. The solution is implemented in C++ and effectively uses a single pass solution to evaluate the winner by comparing neighboring characters in a string.

  • Initialize two integer counters aliceCount and bobCount to zero. These counters are used to record the number of valid moves available to Alice and Bob, respectively.
  • Iterate through the string sequence starting from the second character and ending at the second to last character. This ensures that each character checked has both left and right neighbors.
  • Check if the current character i and its neighbors i-1 and i+1 are the same. If they are:
    • Increase aliceCount by one if the current and neighboring characters are 'A'.
    • Increase bobCount by one if the current and neighboring characters are 'B'.
  • After the loop completes, compare aliceCount and bobCount. Return true if aliceCount is greater than bobCount, indicating Alice wins, otherwise return false, indicating Bob wins or it's a draw.

This approach directly checks each potential move's validity and counts it accordingly, leading to an efficient solution that handles the game logic within a single traversal of the sequence.

java 
class GameResult {
    public boolean determineWinner(String sequence) {
        int scoreA = 0;
        int scoreB = 0;
        
        for (int index = 1; index < sequence.length() - 1; index++) {
            if (sequence.charAt(index - 1) == sequence.charAt(index) && sequence.charAt(index) == sequence.charAt(index + 1)) {
                if (sequence.charAt(index) == 'A') {
                    scoreA++;
                } else {
                    scoreB++;
                }
            }
        }
        
        return scoreA > scoreB;
    }
}

The given Java code defines a class GameResult with a method determineWinner that evaluates a string representing a sequence of colored pieces and determines if the player labeled 'A' can win the game based on removing pieces whose neighbors are of the same color.

  • In the method, scoreA and scoreB are initialized to keep track of the score for player 'A' and player 'B', respectively.
  • The method iterates through the string from the second character to the second-to-last character (inclusive) to check for sequences where a piece is flanked by pieces of the same color.
  • If three consecutive identical characters ('A' or 'B') are found, the score for the respective player is incremented.
  • After the loop, the method returns true if scoreA is greater than scoreB, indicating that player 'A' has more removable colored pieces and hence is considered the winner. Otherwise, it returns false.

The code effectively implements a strategy game score tally based on specified conditions, returning a boolean result to indicate victory.

python 
class Solution:
    def gameWinner(self, colors: str) -> bool:
        counterA = 0
        counterB = 0
        
        for idx in range(1, len(colors) - 1):
            if colors[idx - 1] == colors[idx] == colors[idx + 1]:
                if colors[idx] == "A":
                    counterA += 1
                else:
                    counterB += 1
        
        return counterA > counterB

This Python solution addresses the problem of determining the game winner by counting the opportunities each player has to remove colored pieces from a linear game board, where each piece is either 'A' or 'B'. The main strategy is to iterate through the sequence of colors and check sequences where three consecutive pieces are the same color.

  • Initialize two counters, counterA and counterB, to zero. These will track the count of removable pieces for players A and B, respectively.
  • Iterate through the string colors starting from the second character and ending at the second to last character:
    • Check if the current character and its two neighbors (left and right) are the same.
    • If they are the same and the character is 'A', increment counterA. If the character is 'B', increment counterB.
  • After completing the iteration, compare counterA and counterB.
  • Return True if counterA is greater than counterB (indicating that player A can remove more pieces and is therefore the winner), otherwise return False.

This approach ensures that all potential removal opportunities are counted based on the sequence provided, and the winner is determined based on who has more such opportunities.

Comments

No comments yet.