Sandwiched Chip Duel

Medium

Chips of two colours lie in a row; the string chips lists them from left to right as the letters A and B. Two players take turns, and the first player starts. - The first player may remove an A chip only if both of its neighbours are also A. - The second player may remove a B chip only if both of its neighbours are also B. - Chips at either end of the row can never be removed. After a removal the row closes up. A player who cannot move loses. Both play optimally. Return True if the first player wins and False if the second does.

Example 1

chips="BAAAAB" → True

The first player has two moves (the middle As), the second has none. The first player moves and the second is stuck.

Example 2

chips="AAABBB" → False

Each player has one move. The first uses it, the second uses theirs, and the first is left without a move.

Example 3

chips="AB" → False

There are no inner chips, so the first player loses at once.

Constraints

1 ≤ len(chips) ≤ 10⁵
chips consists of the letters A and B

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Math String Game Theory