Remove Colored Pieces if Both Neighbors are the Same Color

Remove Colored Pieces if Both Neighbors are the Same Color - 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.

Input & Output

Example 1 — Equal Groups

$ Input: colors = "AAABBBAA"

› Output: false

💡 Note: Alice can remove 1 piece from AAA group, Bob can remove 1 piece from BBB group. Since they have equal moves and Alice goes first, Bob makes the last move and wins.

Example 2 — Alice Has More

$ Input: colors = "AA"

› Output: false

💡 Note: No groups of 3+ consecutive pieces exist, so neither player can make any moves. Alice goes first but cannot move, so Bob wins immediately.

Example 3 — Large Alice Group

$ Input: colors = "ABBBBAA"

› Output: false

💡 Note: Only the BBBB group has 4 pieces, giving Bob 2 moves (4-2=2). Alice has no groups of 3+, so Bob wins.

Constraints

1 ≤ colors.length ≤ 10⁵
colors[i] is either 'A' or 'B'

Visualization

Tap to expand

Understanding the Visualization

Input

String of A and B pieces arranged in a line

Process

Players alternate removing pieces when surrounded by same color

Output

True if Alice wins, false if Bob wins

Key Takeaway

🎯 Key Insight: Count total available moves for each player instead of simulating the game turn by turn

Asked in

M Microsoft 12 G Google 8

The key insight is that move order doesn't matter - only the total number of moves each player can make. Count consecutive groups of 3+ same-colored pieces and compare totals. Best approach is Greedy Counting. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Game Simulation	O(n³)	O(n)	Simulate the entire game by alternating turns between Alice and Bob
Greedy Counting	O(n)	O(1)	Count total moves available to each player without simulating the game

Game Simulation — Algorithm Steps

Find all valid moves for current player
Make the first valid move
Switch to other player
Repeat until no moves available

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with the given string

Find Moves

Current player finds valid moves

Make Move

Remove a piece and switch turns

Continue

Repeat until no moves available

Code -

solution.c — C

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

bool solution(char* colors) {
    int len = strlen(colors);
    char* current = malloc((len + 1) * sizeof(char));
    strcpy(current, colors);
    
    bool aliceTurn = true;
    
    while (true) {
        char player = aliceTurn ? 'A' : 'B';
        int movePos = -1;
        int currentLen = strlen(current);
        
        // Find first valid move
        for (int i = 1; i < currentLen - 1; i++) {
            if (current[i] == player && current[i-1] == player && current[i+1] == player) {
                movePos = i;
                break;
            }
        }
        
        if (movePos == -1) {
            bool result = !aliceTurn;
            free(current);
            return result;
        }
        
        // Remove character at movePos
        for (int i = movePos; i < currentLen - 1; i++) {
            current[i] = current[i + 1];
        }
        current[currentLen - 1] = '\0';
        
        aliceTurn = !aliceTurn;
    }
}

int main() {
    char colors[100001];
    fgets(colors, sizeof(colors), stdin);
    colors[strcspn(colors, "\n")] = 0; // Remove newline
    
    bool result = solution(colors);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n turns, we scan n positions and potentially recreate the string of length n

⚠ Quadratic Growth

Space Complexity

O(n)

String modifications create new string instances

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Game Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler