Максимизируйте «10» подпоследовательностей, заменив не более одного 0 на 1

Для заданной двоичной строки S , состоящей только из « 0 » и «1 », задача состоит в том, чтобы найти максимально возможное количество «10» подпоследовательностей, заменив не более одного 0 на 1.

Примеры:

Input: 1110
Output: 3
Explanation: Here initial answer = 3, since pairs: {0, 3}, {1, 3} and {2, 3} initially form the given subsequence. So no need to perform any operations since after performing operation answer would decrease. Hence answer is 3

Input: 101100
Output: 8
Explanation: Here initial answer = 7, since pairs {0, 1}, {0, 4}, {0, 5}, {2, 4}, {2, 5}, {3, 5} and {3, 4} formed the subsequence. If we perform operation on index 1 we get new string as 111100 which gives 8 possible subsequence.

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

Since it’s allowed to convert a value from ‘0’ to ‘1’, we can think greedily to get our answer.

If we change one ‘0’ to ‘1’, It results in the addition of extra subsequences formed due to changing of ‘0’ to ‘1’. However, it also leads to a loss in a certain amount of subsequences that ‘0’ was initially forming with its previous ‘1’s. Hence we need to select a position such that greedily Net profit = gain(from extra good pairs generated) – loss (originally good pairs destroyed) is maximized.

So how do we calculate it efficiently:

For this purpose, we need to create a suffix array that stores the number of ‘0’ to its right in the string so that we can find the profit after converting that ‘0’ to ‘1’. Also, we need to create a prefix array that stores the number of ‘1’ to its left such that we can find loss after converting that ‘0’ to ‘1’.

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

• Создайте массив размером N + 1 для хранения того, сколько нулей появляется после символа.
  • Сначала проверьте последний символ, а затем оставшиеся символы, используя цикл, начиная с (i = n - 2 до 0).
• Опять же, сделайте то же самое для сохранения появления единиц в префиксе любого символа.
• Вычислите исходный ответ, добавив 0 в суффиксе для всех индексов.
• Запустите цикл от i = 0 до N :
  • Рассчитайте максимальную прибыль среди всех индексов.
• Добавьте первоначальный ответ и максимальную прибыль, которая является нашим окончательным ответом, и верните это значение.

Ниже приведена реализация подхода.

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

Статьи по Теме:

• Введение в строки — учебные пособия по структурам данных и алгоритмам