Максимально увеличить длину подпоследовательности, состоящей из одного отдельного символа, можно с помощью K приращений в строке
Для заданной строки S , состоящей из символов нижнего регистра и целого числа K , задача состоит в том, чтобы найти максимальную длину подпоследовательности, состоящей из одного отдельного символа, путем увеличения не более чем K символов.
Примеры:
Input: S = “acscbcca” K = 1
Output: 5
Explanation: Incrementing the character S[4] from ‘b’ to ‘c’, modifies the string to “acscccca”. Therefore, longest subsequence of same characters is “ccccc”. Length of the subsequence is 5.Input: S = “adscassr”, K = 2
Output: 4
Подход: данная проблема может быть решена с помощью техники скользящего окна и сортировки. Следуйте инструкциям, чтобы решить эту проблему:
- Инициализируйте переменные, скажем, start , end и sum равными 0 , в которых хранятся начальные и конечные индексы подпоследовательностей и сумма скользящего окна.
- Инициализируйте переменную, скажем, toINT_MIN , которая хранит длину результирующей самой длинной подпоследовательности.
- Отсортируйте заданную строку S.
- Пройдите по строке в диапазоне [0, N – 1] и выполните следующие шаги:
- Увеличьте значение суммы на значение (S[end] – 'a') .
- Повторяйте цикл до тех пор, пока значение (сумма + K) не станет меньше, чем (S[конец] – 'a') * (конец – начало + 1) , и выполните следующие шаги:
- Уменьшите значение суммы на ( S[start] – 'a') .
- Увеличьте значение start на 1 .
- После вышеуказанных шагов все символы в диапазоне [начало, конец] можно сделать равными, используя не более K приращений. Поэтому обновите значение ans как максимальное значение ans and (end – start + 1) .
- После выполнения вышеуказанных шагов выведите в качестве результата значение ans .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N * log N)
Вспомогательное пространство: O(1)