1062. Colour Removal Duel
A decorator lays a strip of paint tiles, each coloured Red ('R') or Blue ('B'), and the string colors lists them from left to right. Two players, Red and Blue, take turns, and Red moves first. On your turn you must pick one tile of your own colour that has a neighbour on both its left and its right, both of your colour too, and lift it out so the strip closes up. You may never lift a tile of the other colour. A player with no legal move on their turn loses the duel.
Return true if Red wins when both players play perfectly, otherwise false. Aim for a single scan of colors in O(n) time and O(1) extra space.
Example 1
- Input:
- colors = "BRRRRB"
- Output:
- true
- Explanation:
Red has two lifts available (the middle tiles of its run of four) and Blue has none, so Red never runs out of moves first.
Example 2
- Input:
- colors = "RRRBBBBRR"
- Output:
- false
- Explanation:
Red can lift one tile and Blue can lift two, so Red runs out of moves first and loses.
Example 3
- Input:
- colors = "RBRBRB"
- Output:
- false
- Explanation:
No tile has two same-coloured neighbours, so Red cannot move at all and loses immediately.
Constraints
1 ≤ colors.length ≤ 105
colors[i] is either 'R' or 'B'
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)