Лексикографически наименьшая строка с периодом K возможна путем замены символов '?' в заданной строке.

Опубликовано: 22 Сентября, 2022

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

A string is said to be a period of K if and only if the length of the string is a multiple of K and for all possible value of i over the range [0, K) the value S[i + K], S[i + 2*K], S[i + 3*K], …, remains the same.

Примеры:

Input: S = “ab??”, K = 2
Output: abab

Input: S = “??????”, K = 3
Output: aaaaaa

Наивный подход: данный подход также можно решить, сгенерировав все возможные комбинации строк, заменив каждый символ '?' с любыми символами нижнего регистра и вывести эту строку, в которой каждая подстрока размера K одинакова.

Временная сложность: O(26 M ), где M — количество символов «?» в строке С.
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать, просматривая строку таким образом, чтобы просматривались первый, второй, третий и т. д. символы, и если все символы были '?' затем замените его символом «a». В противном случае, если в каждой соответствующей позиции существует только один отдельный символ, замените «?» с этим символом. В противном случае строка не может быть изменена в соответствии с заданными критериями и, следовательно, выведите «-1». Выполните следующие шаги, чтобы решить проблему:

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

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ