Переставьте символы в отсортированной строке так, чтобы никакие пары соседних символов не совпадали.

Дана отсортированная строка S , состоящая из N символов нижнего регистра. Задача состоит в том, чтобы переставить символы в заданной строке так, чтобы никакие два соседних символа не были одинаковыми. Если переставить по заданным критериям невозможно, то выведите «-1» .

Примеры:

Input: S = “aaabc”
Output: abaca

Input: S = “aa”
Output: -1

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

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

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

Временная сложность: O(N), так как мы используем обратную функцию, которая будет стоить O (N) времени.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.