Максимальное количество нулей между двумя единицами в заданном диапазоне для запросов Q

Для заданной двоичной строки S размера N и двухмерного массива Q[][] запросов, состоящего из M пар вида {L, R} , задача для каждого запроса состоит в том, чтобы найти максимальное количество нулей , лежащих между двумя единицами в диапазон [L, R] .

Примеры:

Input: S = “1001010”, Q[][] = {{0, 4}, {0, 5}}
Output: 2 3
Explanation: 
The Queries are performed as per the following:

1. Query(0, 4): Print 2 as there are maximum 2 0’s lying between the indices 0 and 3 in the substring over the range [0, 4] i.e., “10010”. 
2. Query(0, 5): Print 3 as there are maximum 3 0’s lying between the indices 0 and 5 in the substring over the range [0, 5] i.e “100101”.

Input: S = “111”, Q[][] = {{0, 2}}
Output: 0

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы пройти по заданному массиву запросов Q[][] и для каждого запроса вывести максимальное количество нулей между любыми двумя парами единиц , перебирая диапазон [L, R] .

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

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

• Инициализируйте два массива, скажем, leftBound[] и rightBound[] для хранит количество нулей , которые находятся справа от самых последних единиц , и количество нулей , оставшихся до самых последних единиц соответственно.
• Инициализируйте две переменные, скажем, count и total , чтобы обновить массивы leftBound[] и rightBound[] .
• Пройдите по заданной строке S и, если текущий символ равен ' 1 ', присвойте значение curr переменной total . В противном случае увеличьте итоги на 1 , а затем присвойте значение curr для rightBound[i] .
• Обновите значение curr и totals до 0 .
• Пройдите строку в обратном порядке и на каждой итерации, если текущий символ равен ' 1 ', тогда обновите значение curr до общего значения. В противном случае увеличьте значение total на 1 , а затем обновите значение curr до lefttBound[i] .
• После выполнения вышеуказанных шагов пройдитесь по заданному массиву запросов Q[][] и для каждого запроса выведите значение (leftBound[Q[i][0]] + rightBound[Q[i][1]] — всего) как результирующее максимальное количество 0s .

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

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