Количество подстрок в двоичной строке, содержащих больше единиц, чем нулей

Для заданной двоичной строки s задача состоит в том, чтобы вычислить количество таких подстрок, в которых количество единиц строго больше, чем количество нулей .

Примеры

Input: S = “110011”
Output: 11
Explanation: 
Substrings in which the count of 1’s is strictly greater than the count of 0’s are { S[0]}, {S[0], S[1]}, {S[0], S[2]}, {S[0], S[4]}, {S[0], S[5]}, {S[1], S[1]}, {S[1], S[5]}, {S[3], S[5]}, {S[4], S[4]}, {S[4], S[5]}, {S[5], S[5]}.

Input: S = “101”
Output: 3

Наивный подход: самый простой подход к решению проблемы — сгенерировать все подстроки и подсчитать количество единиц и нулей в каждой подстроке. Увеличьте количество тех подстрок, которые содержат количество 1 с больше, чем количество 0 с. Наконец, распечатайте полученное количество.
Временная сложность : O(N ³ )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход можно оптимизировать с помощью алгоритма сортировки слиянием. Выполните следующие действия:

• Инициализируйте массив, скажем, nums[] размера n, где n — длина строки.
• Пересеките строку. Если s[i] == '1' , то сохраните 1 в nums[i] . В противном случае установите nums[i] = -1 .
• Обновите pref[] для хранения суммы префиксов массива nums[] .
• Теперь задача сводится к подсчету количества пар(i, j) в массиве pref[] , где pref[i] < pref[j] и i < j , что аналогично подсчету инверсий в массиве с тыла сторона.
• Верните количество инверсий массива суммы префикса в качестве окончательного ответа.

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

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