Минимальное количество символов, которое необходимо удалить для сортировки двоичной строки в порядке возрастания — набор 2

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

Данная двоичная строка str размера N задача состоит в том, чтобы удалить минимальное количество символов из заданной двоичной строки, чтобы символы в оставшейся строке были отсортированы.

Примеры:

Input: str = “1000101”
Output: 2
Explanation: Removal of the first two occurrences of ‘1’ modifies the string to “00001”, which is a sorted order. The string can also be made “00011” by performing 2 removals. Therefore, the minimum count of characters to be removed is 2.

Input: str = “001111”
Output: 0
Explanation: The string is already sorted. Therefore, the minimum count of character to be removed is 0.

Подход последнего вхождения: оптимизированный подход в линейном времени и постоянном пространстве обсуждается в наборе 1 этой статьи. Здесь мы обсуждаем подход динамического программирования.

Подход динамического программирования: эту проблему можно решить с помощью динамического программирования, наблюдая следующие факты: если требуется удаление K , чтобы отсортировать строку до i -го индекса и

  • Case1: S[i+1] = 1 then minimum number of deletions required to make string sorted till (i+1)th index will also be K as appending 1 to a sorted string will keep string sorted so no more deletion required.
  • Case2: S[i + 1] = 0 then we have two way to make string sorted till (i+1)th index that are
    • either delete all 1’s before (i+1)th index, or
    • delete current 0.

Minimum number of deletion to make string valid till (i+1)th index will be minimum of (numbers of 1’s before (i+1)th index , K+1).

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменные count1 как 0 , а N — это длина строки s .
  • Инициализируйте вектор dp[n+1] со значениями 0.
  • Перебрать диапазон [0, n), используя переменную i , и выполнить следующие задачи:
    • Если s[i] равно 0, то установите dp[i+1] как минимум из count1 или 1 + dp[i].
    • В противном случае установите dp[i+1] как dp[i] и увеличьте значение count1 на 1.
  • После выполнения вышеуказанных шагов выведите значение dp[n] в качестве ответа.

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


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

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