Remove Colored Pieces if Both Neighbors are the Same Color

Medium
1229.

Remove Colored Pieces if Both Neighbors are the Same Color

MediumMathStringGreedyGame TheoryAmazonGoogleMicrosoftYelpMathWorks

Remove Colored Pieces if Both Neighbors are the Same Color is a medium coding problem on strings, math and greedy, asked in Amazon, Google, Microsoft and Yelp interviews.

A row of pieces is described by the string colors, where each piece is either 'A' or 'B'. Alice and Bob take turns removing pieces, Alice first:

  • Alice may remove a piece colored 'A' only if both of its neighbors are also 'A'.
  • Bob may remove a piece colored 'B' only if both of its neighbors are also 'B'.
  • Pieces at either end of the row have only one neighbor, so they can never be removed.

The player who cannot move on their turn loses. Both play optimally. Return true if Alice wins and false if Bob wins.

Example 1

Input
colors = "AAAABBB"
Output
true
Explanation
Alice has two possible removals inside `AAAA`, Bob only one inside `BBB`. Bob runs out first.

Example 2

Input
colors = "AABBBBA"
Output
false
Explanation
Alice has no legal move at all.

Example 3

Input
colors = "ABA"
Output
false

Constraints

  • 1 <= colors.length <= 10^5
  • colors consists of only the letters 'A' and 'B'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} colors
 * @return {boolean}
 */
var winnerOfGame = function(colors) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Remove Colored Pieces if Both Neighbors are the Same Color Solution

Remove Colored Pieces if Both Neighbors are the Same Color solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Remove Colored Pieces if Both Neighbors are the Same Color is a medium coding problem on strings, math and greedy, asked in Amazon, Google, Microsoft and Yelp interviews.

Problem statement

A row of pieces is described by the string colors, where each piece is either 'A' or 'B'. Alice and Bob take turns removing pieces, Alice first:

  • Alice may remove a piece colored 'A' only if both of its neighbors are also 'A'.
  • Bob may remove a piece colored 'B' only if both of its neighbors are also 'B'.
  • Pieces at either end of the row have only one neighbor, so they can never be removed.

The player who cannot move on their turn loses. Both play optimally. Return true if Alice wins and false if Bob wins.

Example 1

Input: colors = "AAAABBB"
Output: true
Explanation: Alice has two possible removals inside `AAAA`, Bob only one inside `BBB`. Bob runs out first.

Example 2

Input: colors = "AABBBBA"
Output: false
Explanation: Alice has no legal move at all.

Example 3

Input: colors = "ABA"
Output: false

Constraints

  • 1 <= colors.length <= 10^5
  • colors consists of only the letters 'A' and 'B'

Hints for Remove Colored Pieces if Both Neighbors are the Same Color

  1. Hint 1

    Does one player's move ever create or destroy a move for the other player?

  2. Hint 2

    Removing an A from the middle of an A block only shortens that block; it never touches a B block, and it never creates a new triple of As.

  3. Hint 3

    So each player has a fixed budget of moves: a block of k equal letters gives k - 2 moves. Alice wins exactly when her budget is strictly larger.

How to solve Remove Colored Pieces if Both Neighbors are the Same Color

The players never interfere: every 'A' removal shortens an A block by one and leaves all B blocks untouched. So each player simply has a fixed number of moves, and Alice needs strictly more.

Approach

  1. Count a, the positions i with colors[i-1] = colors[i] = colors[i+1] = 'A', and b, the same for 'B'.
  2. Return a > b.

Why it works

A block of k consecutive As allows exactly k - 2 removals (each one shrinks the block by one until two remain), whatever order they come in, and nothing Bob does changes that block because he only removes interior Bs. The same holds for Bob. The game is therefore a race: Alice moves on turns 1, 3, 5, … and loses as soon as she needs move a + 1, which happens before Bob needs move b + 1 exactly when a <= b.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Ties go to Bob: with equal budgets Alice runs out first because she moves first.
  • End pieces never count — the scan runs from index 1 to n - 2.
  • There is no need to simulate the game; the budgets are fixed from the start.

Reference solution

Python

def winnerOfGame(colors: str) -> bool:
    a = b = 0
    for i in range(1, len(colors) - 1):
        if colors[i - 1] == colors[i] == colors[i + 1]:
            if colors[i] == "A":
                a += 1
            else:
                b += 1
    return a > b

Java

public static boolean winnerOfGame(String colors) {
    int a = 0, b = 0;
    for (int i = 1; i + 1 < colors.length(); i++) {
        char c = colors.charAt(i);
        if (colors.charAt(i - 1) == c && colors.charAt(i + 1) == c) {
            if (c == 'A') a++;
            else b++;
        }
    }
    return a > b;
}

C++

bool winnerOfGame(string colors) {
    int a = 0, b = 0;
    for (int i = 1; i + 1 < (int)colors.size(); i++) {
        if (colors[i - 1] == colors[i] && colors[i] == colors[i + 1]) {
            if (colors[i] == 'A') a++;
            else b++;
        }
    }
    return a > b;
}

JavaScript

var winnerOfGame = function(colors) {
    var a = 0, b = 0;
    for (var i = 1; i + 1 < colors.length; i++) {
        if (colors[i - 1] === colors[i] && colors[i] === colors[i + 1]) {
            if (colors[i] === "A") a++;
            else b++;
        }
    }
    return a > b;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms