2038. Remove Colored Pieces if Both Neighbors are the Same Color - Explanation

Description

Alice and Bob alternate turns removing pieces from the string colors, with Alice moving first. Alice may remove an A only when its immediate neighbors are both A. Bob may remove a B only when its immediate neighbors are both B. End pieces cannot be removed. The remaining pieces close the gap after a removal.

A player who has no legal move loses. Assuming optimal play, return true if Alice wins and false if Bob wins.

Example 1:

Input: colors = "AAA"

Output: true

Explanation: Alice removes the middle A, leaving AA. Bob has no legal move, so Alice wins.

Example 2:

Input: colors = "AAABBB"

Output: false

Explanation: Alice must remove the middle A, leaving AABBB. Bob removes the middle B, leaving AABB. Alice then has no move and loses.

Example 3:

Input: colors = "AAAABBB"

Output: true

Explanation: Alice can remove two pieces from the initial run of four As, while Bob can remove only one B. After Alice, Bob, and Alice move, Bob has no legal move.

Constraints:

1 <= colors.length <= 100000
Only A and B occur.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

String Manipulation - Iterating through strings and checking character patterns
Two Pointers - Using pointers to track consecutive runs of characters
Greedy Algorithms - Making locally optimal choices to find the global optimum
Game Theory Basics - Understanding turn-based games and win conditions

1. Brute Force

Intuition

We simulate the game turn by turn. Alice looks for a piece 'A' surrounded by two other 'A's and removes it. Then Bob does the same for 'B'. If a player cannot make a move on their turn, they lose. This straightforward simulation mirrors the actual gameplay but is slow because we repeatedly scan and modify the string.

Algorithm

Convert the string to a mutable list.
Alternate turns between Alice ('A') and Bob ('B').
On each turn, scan for a removable piece (one that has the same color on both sides).
If found, remove it and continue. If not found, the current player loses.
Alice wins if Bob cannot move; Bob wins if Alice cannot move.

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        s = list(colors)

        def removeChar(c):
            for i in range(1, len(s) - 1):
                if s[i] != c:
                    continue

                if s[i] == s[i + 1] == s[i - 1]:
                    s.pop(i)
                    return True
            return False

        while True:
            if not removeChar('A'):
                return False
            if not removeChar('B'):
                return True

        return False

public class Solution {
    public boolean winnerOfGame(String colors) {
        StringBuilder s = new StringBuilder(colors);

        while (true) {
            if (!removeChar(s, 'A')) return false;
            if (!removeChar(s, 'B')) return true;
        }
    }

    private boolean removeChar(StringBuilder s, char c) {
        for (int i = 1; i < s.length() - 1; i++) {
            if (s.charAt(i) != c) continue;

            if (s.charAt(i - 1) == c && s.charAt(i + 1) == c) {
                s.deleteCharAt(i);
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool winnerOfGame(string colors) {
        while (true) {
            if (!removeChar(colors, 'A')) return false;
            if (!removeChar(colors, 'B')) return true;
        }
    }

private:
    bool removeChar(string& s, char c) {
        for (int i = 1; i < s.size() - 1; i++) {
            if (s[i] != c) continue;

            if (s[i - 1] == c && s[i + 1] == c) {
                s.erase(i, 1);
                return true;
            }
        }
        return false;
    }
};

class Solution {
    /**
     * @param {string} colors
     * @return {boolean}
     */
    winnerOfGame(colors) {
        let s = colors.split('');

        const removeChar = (c) => {
            for (let i = 1; i < s.length - 1; i++) {
                if (s[i] !== c) continue;

                if (s[i - 1] === c && s[i + 1] === c) {
                    s.splice(i, 1);
                    return true;
                }
            }
            return false;
        };

        while (true) {
            if (!removeChar('A')) return false;
            if (!removeChar('B')) return true;
        }
    }
}

public class Solution {
    public bool WinnerOfGame(string colors) {
        List<char> s = new List<char>(colors.ToCharArray());

        while (true) {
            if (!RemoveChar(s, 'A')) return false;
            if (!RemoveChar(s, 'B')) return true;
        }
    }

    private bool RemoveChar(List<char> s, char c) {
        for (int i = 1; i < s.Count - 1; i++) {
            if (s[i] != c) continue;

            if (s[i - 1] == c && s[i + 1] == c) {
                s.RemoveAt(i);
                return true;
            }
        }
        return false;
    }
}

func winnerOfGame(colors string) bool {
    s := []byte(colors)

    removeChar := func(c byte) bool {
        for i := 1; i < len(s)-1; i++ {
            if s[i] != c {
                continue
            }

            if s[i-1] == c && s[i+1] == c {
                s = append(s[:i], s[i+1:]...)
                return true
            }
        }
        return false
    }

    for {
        if !removeChar('A') {
            return false
        }
        if !removeChar('B') {
            return true
        }
    }
}

class Solution {
    fun winnerOfGame(colors: String): Boolean {
        val s = StringBuilder(colors)

        fun removeChar(c: Char): Boolean {
            for (i in 1 until s.length - 1) {
                if (s[i] != c) continue

                if (s[i - 1] == c && s[i + 1] == c) {
                    s.deleteCharAt(i)
                    return true
                }
            }
            return false
        }

        while (true) {
            if (!removeChar('A')) return false
            if (!removeChar('B')) return true
        }
    }
}

class Solution {
    func winnerOfGame(_ colors: String) -> Bool {
        var s = Array(colors)

        func removeChar(_ c: Character) -> Bool {
            for i in 1..<s.count - 1 {
                if s[i] != c { continue }

                if s[i - 1] == c && s[i + 1] == c {
                    s.remove(at: i)
                    return true
                }
            }
            return false
        }

        while true {
            if !removeChar("A") { return false }
            if !removeChar("B") { return true }
        }
    }
}

impl Solution {
    pub fn winner_of_game(colors: String) -> bool {
        let mut s: Vec<u8> = colors.into_bytes();

        fn remove_char(s: &mut Vec<u8>, c: u8) -> bool {
            let mut i = 1;
            while i < s.len().saturating_sub(1) {
                if s[i] != c {
                    i += 1;
                    continue;
                }
                if s[i - 1] == c && s[i + 1] == c {
                    s.remove(i);
                    return true;
                }
                i += 1;
            }
            false
        }

        loop {
            if !remove_char(&mut s, b'A') { return false; }
            if !remove_char(&mut s, b'B') { return true; }
        }
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Greedy + Two Pointers

Intuition

The key insight is that each player's moves are independent. Removing an 'A' from a sequence of A's doesn't affect Bob's sequences of B's, and vice versa. So instead of simulating the game, we can count how many moves each player has available. For a run of consecutive same-colored pieces of length k, a player can remove k - 2 pieces (since they need neighbors on both sides). Alice wins if she has more moves than Bob.

Algorithm

Use two pointers to track consecutive runs of the same color.
For each position, calculate how many "extra" pieces exist beyond the first two in the current run.
Add these extras to Alice's count if the color is 'A', or Bob's count if 'B'.
Return true if Alice has more moves than Bob.

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        alice = bob = l = 0

        for r in range(len(colors)):
            if colors[l] != colors[r]:
                l = r

            extra = r - l - 1
            if extra > 0:
                if colors[l] == 'A':
                    alice += 1
                else:
                    bob += 1

        return alice > bob

public class Solution {
    public boolean winnerOfGame(String colors) {
        int alice = 0, bob = 0, l = 0;

        for (int r = 0; r < colors.length(); r++) {
            if (colors.charAt(l) != colors.charAt(r)) {
                l = r;
            }

            int extra = r - l - 1;
            if (extra > 0) {
                if (colors.charAt(l) == 'A') {
                    alice++;
                } else {
                    bob++;
                }
            }
        }

        return alice > bob;
    }
}

class Solution {
public:
    bool winnerOfGame(string colors) {
        int alice = 0, bob = 0, l = 0;

        for (int r = 0; r < colors.size(); r++) {
            if (colors[l] != colors[r]) {
                l = r;
            }

            int extra = r - l - 1;
            if (extra > 0) {
                if (colors[l] == 'A') {
                    alice++;
                } else {
                    bob++;
                }
            }
        }

        return alice > bob;
    }
};

class Solution {
    /**
     * @param {string} colors
     * @return {boolean}
     */
    winnerOfGame(colors) {
        let alice = 0,
            bob = 0,
            l = 0;

        for (let r = 0; r < colors.length; r++) {
            if (colors[l] !== colors[r]) {
                l = r;
            }

            let extra = r - l - 1;
            if (extra > 0) {
                if (colors[l] === 'A') {
                    alice++;
                } else {
                    bob++;
                }
            }
        }

        return alice > bob;
    }
}

public class Solution {
    public bool WinnerOfGame(string colors) {
        int alice = 0, bob = 0, l = 0;

        for (int r = 0; r < colors.Length; r++) {
            if (colors[l] != colors[r]) {
                l = r;
            }

            int extra = r - l - 1;
            if (extra > 0) {
                if (colors[l] == 'A') {
                    alice++;
                } else {
                    bob++;
                }
            }
        }

        return alice > bob;
    }
}

func winnerOfGame(colors string) bool {
    alice, bob, l := 0, 0, 0

    for r := 0; r < len(colors); r++ {
        if colors[l] != colors[r] {
            l = r
        }

        extra := r - l - 1
        if extra > 0 {
            if colors[l] == 'A' {
                alice++
            } else {
                bob++
            }
        }
    }

    return alice > bob
}

class Solution {
    fun winnerOfGame(colors: String): Boolean {
        var alice = 0
        var bob = 0
        var l = 0

        for (r in colors.indices) {
            if (colors[l] != colors[r]) {
                l = r
            }

            val extra = r - l - 1
            if (extra > 0) {
                if (colors[l] == 'A') {
                    alice++
                } else {
                    bob++
                }
            }
        }

        return alice > bob
    }
}

class Solution {
    func winnerOfGame(_ colors: String) -> Bool {
        var alice = 0, bob = 0, l = 0
        let chars = Array(colors)

        for r in 0..<chars.count {
            if chars[l] != chars[r] {
                l = r
            }

            let extra = r - l - 1
            if extra > 0 {
                if chars[l] == "A" {
                    alice += 1
                } else {
                    bob += 1
                }
            }
        }

        return alice > bob
    }
}

impl Solution {
    pub fn winner_of_game(colors: String) -> bool {
        let colors = colors.as_bytes();
        let mut alice = 0i32;
        let mut bob = 0i32;
        let mut l = 0usize;

        for r in 0..colors.len() {
            if colors[l] != colors[r] {
                l = r;
            }
            let extra = r as i32 - l as i32 - 1;
            if extra > 0 {
                if colors[l] == b'A' {
                    alice += 1;
                } else {
                    bob += 1;
                }
            }
        }

        alice > bob
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

3. Greedy

Intuition

This is a cleaner way to count available moves. For each position in the middle of the string, we check if it forms a "triplet" of same-colored pieces. Each such triplet represents one potential move for that player. Since removing a piece from a longer run still leaves valid triplets, we simply count all triplet centers for each player.

Algorithm

Initialize counters for Alice and Bob.
Iterate through positions 1 to n-2 (excluding endpoints).
At each position, check if the current piece matches both its neighbors.
If so, increment Alice's counter for 'A' or Bob's counter for 'B'.
Return true if Alice's count exceeds Bob's count.

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        alice, bob = 0, 0

        for i in range(1, len(colors) - 1):
            if colors[i - 1] == colors[i] == colors[i + 1]:
                if colors[i] == 'A':
                    alice += 1
                if colors[i] == 'B':
                    bob += 1

        return alice > bob

public class Solution {
    public boolean winnerOfGame(String colors) {
        int alice = 0, bob = 0;

        for (int i = 1; i < colors.length() - 1; i++) {
            if (colors.charAt(i - 1) == colors.charAt(i) &&
                colors.charAt(i) == colors.charAt(i + 1)) {
                if (colors.charAt(i) == 'A') {
                    alice++;
                }
                if (colors.charAt(i) == 'B') {
                    bob++;
                }
            }
        }

        return alice > bob;
    }
}

class Solution {
public:
    bool winnerOfGame(string colors) {
        int alice = 0, bob = 0;

        for (int i = 1; i < colors.size() - 1; i++) {
            if (colors[i - 1] == colors[i] && colors[i] == colors[i + 1]) {
                if (colors[i] == 'A') {
                    alice++;
                }
                if (colors[i] == 'B') {
                    bob++;
                }
            }
        }

        return alice > bob;
    }
};

class Solution {
    /**
     * @param {string} colors
     * @return {boolean}
     */
    winnerOfGame(colors) {
        let alice = 0,
            bob = 0;

        for (let i = 1; i < colors.length - 1; i++) {
            if (colors[i - 1] === colors[i] && colors[i] === colors[i + 1]) {
                if (colors[i] === 'A') {
                    alice++;
                }
                if (colors[i] === 'B') {
                    bob++;
                }
            }
        }

        return alice > bob;
    }
}

public class Solution {
    public bool WinnerOfGame(string colors) {
        int alice = 0, bob = 0;

        for (int i = 1; i < colors.Length - 1; i++) {
            if (colors[i - 1] == colors[i] && colors[i] == colors[i + 1]) {
                if (colors[i] == 'A') {
                    alice++;
                }
                if (colors[i] == 'B') {
                    bob++;
                }
            }
        }

        return alice > bob;
    }
}

class Solution {
    fun winnerOfGame(colors: String): Boolean {
        var alice = 0
        var bob = 0

        for (i in 1 until colors.length - 1) {
            if (colors[i - 1] == colors[i] && colors[i] == colors[i + 1]) {
                if (colors[i] == 'A') {
                    alice++
                }
                if (colors[i] == 'B') {
                    bob++
                }
            }
        }

        return alice > bob
    }
}

class Solution {
    func winnerOfGame(_ colors: String) -> Bool {
        var alice = 0, bob = 0
        let chars = Array(colors)

        for i in 1..<chars.count - 1 {
            if chars[i - 1] == chars[i] && chars[i] == chars[i + 1] {
                if chars[i] == "A" {
                    alice += 1
                }
                if chars[i] == "B" {
                    bob += 1
                }
            }
        }

        return alice > bob
    }
}

impl Solution {
    pub fn winner_of_game(colors: String) -> bool {
        let colors = colors.as_bytes();
        let mut alice = 0i32;
        let mut bob = 0i32;

        for i in 1..colors.len().saturating_sub(1) {
            if colors[i - 1] == colors[i] && colors[i] == colors[i + 1] {
                if colors[i] == b'A' {
                    alice += 1;
                }
                if colors[i] == b'B' {
                    bob += 1;
                }
            }
        }

        alice > bob
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Simulating the Game Turn by Turn

A common mistake is to simulate the actual game by removing pieces one at a time and alternating turns. This leads to O(n^2) time complexity because each removal requires scanning and modifying the string. The key insight is that removing an 'A' from a sequence of A's doesn't affect Bob's available moves on B sequences, and vice versa. Instead of simulating, simply count the available moves for each player upfront.

Miscounting Available Moves

When counting moves, remember that a player can only remove a piece if it has neighbors of the same color on both sides. For a run of k consecutive same-colored pieces, the number of removable pieces is k - 2 (not k or k - 1). A run of length 1 or 2 gives zero moves. Some solutions incorrectly count individual pieces or forget to subtract 2 for the boundary pieces that cannot be removed.

Using the Wrong Win Condition

The problem asks if Alice wins, and Alice moves first. Some solutions return alice >= bob instead of alice > bob. Since Alice needs strictly more moves than Bob to win (she goes first, so if they have equal moves, Bob makes the last move and Alice loses), the correct condition is alice > bob.