Если начальная или конечная строка состоит из одинаковых символов, или же она имеет чётную длину, и в ней чередуются два символа, то её невозможно получить ни из какой другой и из неё невозможно получить никакую другую. Поэтому в этом случае преобразование возможно, лишь если начальная и конечная строки совпадают: тогда можно просто ничего не делать.
В остальных случаях преобразование всегда возможно. Найдём в первой строке строке символ $$$s_i$$$, отличный от двух его соседей (если такого нет, то это случай из предыдущего абзаца). Начиная с него и идя по часовой стрелке, будем каждый символ $$$s_j$$$ заменять на любой символ, отличный от $$$s_{j - 2}$$$ и $$$s_{j + 2}$$$ (индексы рассматриваются по модулю $$$n$$$). При $$$j = i$$$ мы знаем, что вокруг $$$s_j$$$ различные символы, а при остальных $$$j$$$, делая непосредственно перед этим замену символа $$$s_{j - 1}$$$, мы сделали так, чтобы он отличался от $$$s_{j + 1}$$$. После этих $$$n$$$ операций мы добились того, что каждая пара символов, стоящих через один, различна.
Теперь найдём во второй строке символ $$$t_k$$$, у которого различны соседи (опять же, такой есть). Начиная с $$$j = k + 1$$$, мы будем заменять каждый символ $$$s_j$$$ на любой символ, отличный от $$$t_{j - 2}$$$ и $$$s_{j + 2}$$$. Снова поймём, что так можно делать: во время первой операции все пары символов, стоящих через один, различны, поэтому можно изменить любой символ, а во время каждой следующей операции $$$s_j$$$ можно поменять, так как прямо перед этим $$$s_{j - 1}$$$ был заменён на какой-то символ, не равный $$$s_{j + 1}$$$. Вторым проходом мы добились, что каждый символ $$$s_j$$$ не равен $$$t_{j - 2}$$$. Кроме того, последний символ, который мы изменяли, то есть $$$s_k$$$, не равен $$$s_{k + 2}$$$.
Последним, третьим проходом, мы будем, начиная с символа $$$s_{k + 1}$$$, заменять все символы $$$s_j$$$ на $$$t_j$$$. Первую такую операцию над символом $$$s_{k + 1}$$$ можно сделать, так как $$$s_k$$$ и $$$s_{k + 2}$$$ различны. Каждая следующая операция над очередным символом $$$s_j$$$ возможна, так как по построению из предыдущего абзаца символ $$$s_{j + 1}$$$ отличается от $$$t_{j - 1} = s_{j - 1}$$$ (ведь в течение третьего прохода символ $$$s_{j + 1}$$$ мы ещё поменять не успели). Исключением является лишь символ $$$s_k$$$, ведь, дойдя до него, мы уже успели поменять символ $$$s_{k + 1}$$$ на $$$t_{k + 1}$$$. Тем не менее, мы сможем поменять $$$s_k$$$ на $$$t_k$$$, поскольку $$$s_{k - 1} = t_{k - 1} \ne t_{k + 1} = s_{k + 1}$$$.
Таким образом, за $$$3n$$$ операций мы точно сможем из одной строки получить другую.