Проверьте, можно ли получить перестановку S2, добавив или удалив символы из S1.

Даны две строки S1 и S2 , состоящие из N и M символов, задача состоит в том, чтобы проверить, можно ли сделать строку S1 равной любой перестановке S2 после добавления или удаления символа простое число раз из строки S1 . Если это возможно, то выведите «Да» . В противном случае выведите «Нет» .

Примеры:

Input: S1 = “gekforgk”, S2 = “geeksforgeeks”
Output: Yes
Explanation:
If character ‘e’ is added 3(which is a prime number) times and character ‘s’ is added two(which is a prime number) times to S1 it will be “gekforgkeeess” which is a permutation of S2. Therefore, print Yes.

Input: S1 = “xyzzyzz”, S2 = “xyy”
Output: No

Подход: Данную задачу можно решить, подсчитав частоты символов в строках S1 и S2 , и если разница в частоте любых символов не является простой, выведите «Нет» . В противном случае выведите «Да» . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте массив частот, скажем, freq[] размером 256 .
• Перебрать символы строки S1 и для каждого символа уменьшить частоту символа в freq[] на 1 .
• Перебрать символы строки S2 и для каждого символа увеличить частоту символа в freq[] на 1 .
• После выполнения вышеуказанных шагов, если абсолютные значения всех элементов в freq[] являются простыми, выведите «Да» . В противном случае выведите «Нет» .

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

Временная сложность: O(max(N, M))
Вспомогательное пространство: O(1)