Найдите анаграмму заданной строки, имеющей разные символы в соответствующих индексах

Для заданной строки S , состоящей из N символов, задача состоит в том, чтобы найти анаграмму данной строки S , в которой символы с теми же индексами отличаются от исходной строки.

Примеры:

Input: S = “geek”
Output: egke
Explanation:
The anagram of the given string such that all the characters at all the corresponding indices are not same is “egke”.  

Input: S = “aaaa”
Output: -1

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

• Инициализировать строку, скажем, T , в которой хранится заданная строка S.
• Инициализируйте два указателя, скажем, i и j как 0 и (N – 1) соответственно.
• Повторяйте до тех пор, пока значение i не станет меньше N , а j не станет неотрицательным, и выполните следующие шаги:
  1. Если символы S[i] и S[j] не совпадают и пары символов (S[i], T[j]) и (T[i], S[j]) также не совпадают( которые гарантируют, что символы после операции замены станут такими же, как оригинал), затем поменяйте местами символы (S[i], S[j]) и обновите значение j до (N – 1) .
  2. В противном случае увеличьте значение i на 1 .
• Если в строке нечетное количество символов, а символы в средних индексах равны, выполните операцию замены, как показано в приведенных выше шагах.
• После выполнения вышеуказанных шагов, если символы в соответствующих индексах строки S и T не совпадают, то выведите строку S как результирующую строку. В противном случае выведите «-1» .

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

Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)