Минимизируйте длину строки, удалив подстроку одного и того же символа, когда разрешено K флипов

Опубликовано: 27 Февраля, 2023

Учитывая двоичную строку, состоящую только из «0» и «1» и целое число K , задача состоит в том, чтобы минимизировать строку, насколько это возможно, удалив подстроку одного и того же символа, когда вы можете перевернуть не более K символов.

Примеры:

Input: S = “0110”,  K = 2
Output: 0
Explanation: We can make two ‘0’ s into ‘1’ or vice versa. 
So we can delete all the four characters and 
the remaining size of the string is 0

Input: S = “111”, K = 1
Output: 0

Подход: Чтобы решить проблему, следуйте следующей идее:

As we have to minimize the string by deleting characters so we have to delete the maximum length of substring consisting of equal letters. So, we can understand the minimum length will range from 1 to the size of the string(let’s say n). 

Now if we apply binary search on this range of length and  check for a shorter length until it is out of range, we can get the answer.

Следуйте инструкциям, чтобы решить проблему:

  • Сначала для бинарного поиска мы определим наш диапазон от Low = 1 до High = n (размер строки).
    • Затем, найдя середину, мы будем продолжать передавать середину для проверки функции, чтобы получить один из возможных ответов, и продолжать увеличивать младшую до средней + 1 , поскольку мы хотим максимальную длину
    • В функции проверки сначала мы создадим массив размеров до 2 для подсчета «0» и «1».
    • Затем мы будем считать «0» и «1» и сохранять в этом массиве счетчиков, и если минимум счетчика обоих элементов меньше K, это означает, что мы можем изменить эти символы на один и тот же символ, чтобы увеличить качество нить.
    • После этого окно сдвинется на средний (предельный) размер и уменьшится количество первого элемента окна, поскольку окна больше нет, и увеличится количество нового элемента , поскольку это новый и последний элемент окна.
    • Теперь мы снова проверим минимальное количество «0» и «1», если оно меньше или равно K , затем вернем true, иначе false
    • Мы будем хранить все возможные ответы на переменную ans , и когда низкий уровень ≥ высокий, цикл завершится, и у нас будет максимально возможная длина для удаления, сохраненная в переменной ans .
  • Теперь мы вычтем максимальную длину из размера массива, чтобы получить размер нашей минимизированной строки.

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

Временная сложность: O(N * logN), так как размер строки равен N, и мы применяем бинарный поиск со сложностью logN. Итак, сложность O(N*logN).
Вспомогательное пространство: O(1)

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