Дуэль за зажатые фишки

Средняя

В ряд выложены фишки двух цветов; строка chips описывает их слева направо буквами A и B. Двое играют, делая ходы по очереди, первый начинает. - Первый игрок может снять фишку A, только если обе её соседки тоже A. - Второй игрок может снять фишку B, только если обе её соседки тоже B. - Крайние фишки снимать нельзя. После снятия ряд смыкается. Кто не может сделать ход, проигрывает. Оба играют оптимально. Верните True, если побеждает первый игрок, и False, если второй.

Пример 1

chips="BAAAAB" → True

У первого игрока два хода (средние A), у второго — ни одного. Первый ходит, второму ответить нечем.

Пример 2

chips="AAABBB" → False

У каждого по одному ходу. Первый тратит свой, второй — свой, и первому ходить нечем.

Пример 3

chips="AB" → False

Фишек внутри ряда нет, первый игрок проигрывает сразу.

Ограничения

1 ≤ len(chips) ≤ 10⁵
chips состоит из букв A и B

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Greedy Math String Game Theory

Вход

chips="BAAAAB"

Ожидается

True

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 185 тестов на сервере, включая скрытые.