Задача №114935. Преобразование строки
Даны две строки \(S\) и \(T\) из строчных букв английского алфавита.
Посмотрим на следующий процесс. Рассмотрим не более одного раза каждый символ, хотя бы где-то входящий в первую строку. После чего, для рассматриваемого символа \(x\) определим другой символ \(p(x) \neq x\) и заменим некоторые вхождения \(x\) в \(S\) на \(p(x)\). Определите, возможно ли в ходе такого процесса получить из строки \(S\) строку \(T\). При этом разные символы можно заменять на один и тот же символ или на символ, который заменяться не будет.
Например, пусть \(S = \) «aabab», \(T = \) «abbbc». Из \(S\) можно получить \(T\), если выбрать p('a') = 'b' , p('b') = 'c' и заменить второе и третье вхождение 'a' на p('a') , второе вхождение 'b' на p('b') .
А если \(S = \) «aabaс», \(T = \) «bbbbb», то все вхождения 'a' и 'c' были заменены на 'b'.
В первой строке вам дано число \(n\) \((1 \leqslant n \leqslant 200\,000)\). Во второй строке задана \(S\). В третьей строке задана \(T\). Обе строки имеют длину \(n\) и состоят только из букв от 'a' до 'z' .
Если возможно осуществить описанный процесс так, чтобы из \(S\) получилась \(T\), выведите «YES», на следующей строке выведите \(m\) – количество различных символов \(S\), которые хотя бы раз заменялись. Обозначим эти символы за \(c_1,\ c_2,\ \ldots \ c_m\). После чего выведите \(m\) строк. На \(i\)-й строке необходимо вывести символы \(c_i\) и \(p(c_i)\) через пробел. Если это сделать невозможно, выведите «NO».
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие, когда обе программы состоят только из символов 'a' и 'b', наберут не менее 20 баллов.
Решения, корректно работающие, когда обе программы состоят только из символов 'a', 'b', 'c', наберут не менее 40 баллов.
Решения, корректно работающие при \(n \leqslant 1\,000\) наберут не менее 60 баллов.
Решения, корркетно работающие только для случая, когда описанными заменами из одной строки вторую получить невозможно, будут оцениваться в 0 баллов.
3 aab abb
YES 1 a b
4 aabb eeff
YES 2 a e b f
3 abc abc
YES 0
5 bcbdb xcydz
NO
3 abc ddd
YES 3 a d b d c d
3 abc aaa
YES 2 b a c a