Сведите к минимуму максимальное количество оставшихся нулей или удаленных единиц из двоичной строки.

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

Вам дана двоичная строка S размера N , состоящая из символов 0 и/или 1 . Вы можете удалить несколько символов из начала или конца строки. Задача состоит в том, чтобы найти стоимость удаления, где стоимость является максимальным из следующих двух значений:

  • Количество символов 0, оставшихся в строке.
  • Количество символов 1, удаленных из строки.

Примеры:

Input: S = “101110110”
Output: 1
Explanation: It is possible to remove two characters from the beginning and one character from the end. Only one 1 is deleted, only one 0 remains. So the cost is 1

Input: S = “1001001001001”
Output: 3
Explanation: It is possible to remove three characters from the beginning and six characters from the end. Two 0 remains, three 1 are deleted. So the cost is 3

Input: S = “0000111111”
Output: 0
Explanation: It is optimal to remove four characters from the beginning.

Input: S = “00000”
Output: 0
Explanation: It is optimal to remove the whole string.

Подход: Задача может быть решена на основе следующей идеи:

Say there are total X number of 0s in S. So if we do not delete any of the characters the maximum cost will be X. We have to delete some 0 to minimize the cost.

The optimal way is to delete at most X elements in total. If we delete more than X elements, there is a possibility of deleting more than X 1s which will result in more cost. Also we cannot reduce the cost by deleting more than X characters.

Proof: Say there were Y 1s deleted among the total X deleted characters. Now to reduce the cost we can only delete 0s from the string. There can at max be Y 0s that are not deleted from the string. So the present cost is max(Y, Y) = Y. If we delete those Y then no 0 will be left but already Y 1s are deleted. So the cost will be max(0, Y) = Y.

Для эффективной реализации идеи выполните следующие шаги:

  • Переберите строку и найдите общее количество нулей (скажем, count0 ).
  • Сохраняйте количество нулей префикса и количество нулей суффикса в двух массивах (например , prefixCountZero[] и suffixCountZero[] ).
  • Итерируйте от нуля до count0 и рассчитайте текущую стоимость как:
    • currentCost = count0 — prefixCountZero [i — 1] — suffixCountZero [n — (count0 — i)]
    • Минимум всех значений currentCost будет ответом.

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

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

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