Решение задачи

Алгоритм решения задачи:

Ключевые наблюдения:

Есть три типа символов: «L», «R», «X».

Замена XL на LX = сдвинуть L на один влево

Замена RX на XR = сдвинуть R вправо на один

Если мы удалим все X в обеих строках, результирующие строки должны быть одинаковыми.

Дополнительные наблюдения:

Поскольку ход всегда включает X, L или R не могут пройти через другие L или R.

Поскольку буква L может перемещаться только вправо, для каждого вхождения буквы L в начальной строке ее положение должно быть таким же или левее соответствующей буквы L в конечной строке.

Реализация

Сначала мы сравниваем две строки с удаленным X. Это проверяет правильность относительного положения между Ls и Rs.

Затем мы находим индексы для каждого вхождения L и проверяем условие на рисунке выше. Затем мы делаем то же самое для R.