Максимально увеличить количество удалений миноритарных символов, которые можно выполнить из заданной подстроки Binary String.

Питон

Дана двоичная строка str размера N . Выберите любую подстроку из строки и удалите все вхождения миноритарного символа (т.е. символа с меньшей частотой) из подстроки. Задача состоит в том, чтобы узнать максимальное количество символов, которое можно удалить при выполнении одной такой операции.

Примечание. Если в какой-либо подстроке есть как «0», так и «1» в одних и тех же числах, то ни один символ не может быть удален.

Примеры:

Input: str = “01”
Output: 0
Explanation: No character can be removed.
The substrings are “0”, “1” and “01”.
For “0” minority character is ‘1’ and removing that from this substring is not possible as no ‘1’ here.
Same for the substring “1”. And substring “01” has no minority element.
The occurrences of both ‘1’ and ‘0’ are same in “01” substring.

Input: str = “00110001000”
Output: 3
Explanation: Remove all 1s from the substring “1100010”.

Подход: Ниже приведены случаи максимально возможных удалений.

• Случай-1: когда все 0 или 1 могут быть удалены. Когда общее количество «0» и « 1» не совпадает, выберите всю строку и удалите все вхождения элемента меньшинства.
• Случай-2: когда оба символа находятся под одним и тем же номером. Здесь выбор всей строки не позволит удалить какой-либо символ. Итак, возьмите подстроку таким образом, чтобы количество одного символа было таким же, как его количество в реальной строке, а для другого - на единицу меньше. Итак, возможные удаления (количество любых символов во всей строке — 1) .
• Случай 3: когда строка содержит только один тип символов. Тогда никакое удаление невозможно.

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

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