Минимальное значение K такое, что каждая подстрока размера K имеет заданный символ
Дана строка строчных букв 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)