Новелла про осень

Автор задачи и разработчик: Даниил Орешников

Докажем следующий факт: если в новелле есть пара соседних букв $$$c_1$$$ и $$$c_2$$$, которые не являются соседними на клавиатуре, то ее нельзя напечатать, а иначе — можно. Действительно, после того, как будет напечатан символ $$$c_1$$$, палец писателя обязательно будет расположен на клавише с символом $$$c_1$$$. После чего, не печатая следующий символ, писатель может переместить палец только на другие клавиши с символом $$$c_1$$$. А для того, чтобы напечатать $$$c_2$$$, необходимо, чтобы клавиша с таким символом шла сразу после текущей.

В обратную сторону аналогично — если каждая пара соседних символов в новелле встречается подряд на клавиатуре, то чтобы напечатать очередной символ, достаточно переместить палец на первую клавишу соответствующей пары $$$(c_1, c_2)$$$, и нажать следующую по кругу клавишу.

Таким образом, необходимо и достаточно проверить, что любая пара соседних символов в новелле встречается на клавиатуре на соседних позициях.

Для этого воспользуемся структурой данных «множество» (unordered_set, HashSet, set). Положим в множество все пары соседних символов на клавиатуре, после чего так же проитерируемся по всем парам соседних символов в новелле, и проверим принадлежность их пары множеству.

Время работы такого решения — $$$\mathcal{O}(n + |s|)$$$.