Сведите к минимуму максимальное количество оставшихся нулей или удаленных единиц из двоичной строки.
Вам дана двоичная строка 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 1Input: 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 3Input: 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)