Проверьте, можно ли преобразовать строку A в строку B, изменив A[i] на A[i+1] или A[i]..A[i+K-1] на A[i]+1 каждый

Имея две строки A и B , каждая из которых имеет длину N и целое число K , задача состоит в том, чтобы найти, можно ли преобразовать строку A в строку B , используя следующие операции любое количество раз:

• Type1 : выберите индекс i и поменяйте местами A _i и A _i+1
• Type2 : Выберите индекс i , и если A _i, A _i+1 , …, A _i+K-1 равны некоторому символу ch (ch ≠ z) , замените каждый символ его следующим символом (ch+1) , например: «d» заменяется на «e» и так далее.

Примеры:

Input: N = 4, A = “abba”, B = “azza”, K = 2 
Output: Yes
Explanation: Using second operation, we can convert the same characters to their next character,  
and thus get the required string B.
“abba” -> “acca” -> “adda” -> . . . -> “azza”

Input: N = 2, A = “zz”, B = “aa”, K = 1
Output: No

Подход: Наблюдая за работой type1 , становится очевидным, что после некоторой конечной последовательности перестановок строку можно переупорядочить любым способом. Таким образом, при работе второго типа можно не беспокоиться о том, что символы будут соседними (поскольку переупорядочивание строк может быть выполнено в любое время), поэтому имеет значение только частота символов. Ниже приведены шаги, которые необходимо выполнить:

• Итак, чтобы преобразовать строку A в строку B , нужно сделать частоты каждого символа алфавита равными, а затем переупорядочить строку с помощью операции первого типа .
• Если для любого символа i любое недостаточное количество вхождений ( частота _{i, A} < частота _{i, B} ) или если оставшиеся вхождения символа, которые не могут быть преобразованы в следующий символ ( частота _{i, A} – частота _{i, B} ), не являются кратно K (поскольку для преобразования символа в его следующую длину символа требуется больше K ), тогда ответ будет НЕТ , иначе ДА .

Ниже приведена реализация вышеуказанного подхода:

Сложность времени: НА)
Вспомогательное пространство: НА)