Минимальное значение K такое, что каждая подстрока размера K имеет заданный символ

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

Дана строка строчных букв S символ c . Задача состоит в том, чтобы найти минимальное K такое, что каждая подстрока длины K содержит заданный символ c . Если такой K невозможен, вернуть -1 .
Примеры:

Input: S = “abdegb”, ch = ‘b’
Output: 4 
Explanation:
Consider the value of K as 4. Now, every substring of size K(= 4) are {“abde”, “bdeg”, “degb” } has the character ch(= b’).

Input: S = “abfge”, ch = ‘m’
Output : -1

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы выполнить итерацию для всех возможных размеров подстрок в диапазоне [1, N] и проверить, какое минимальное значение K удовлетворяет заданным критериям. Если такого значения K не существует, то выведите «-1» .

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

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

  • Инициализируйте переменную, скажем, maxDifference как -1 , которая хранит результирующее значение K .
  • Инициализируйте переменную, скажем, предыдущую как 0 , которая хранит предыдущее вхождение символа ch в строку S.
  • Пройдите заданную строку S , используя переменную i , и если текущий символ — ch , то обновите значение maxDifference до максимума maxDifference и (i — предыдущее) , а значение предыдущего — до i .
  • После выполнения вышеуказанных шагов выведите в качестве результата значение maxDifference .

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

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

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