You are given a binary string s.
Return the number of substrings with dominant ones.
A string has dominant ones if the number of ones in the string is greater than or equal to the square of the number of zeros in the string.
Example 1:
Input: s = "00011"
Output: 5
Explanation:
The substrings with dominant ones are shown in the table below.
ijs[i..j]Number of ZerosNumber of Ones
Example 2:
Input: s = "101101"
Output: 16
Explanation:
The substrings with non-dominant ones are shown in the table below.
Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.
ijs[i..j]Number of ZerosNumber of Ones
Constraints:
1 <= s.length <= 4 * 10^4
s consists only of characters '0' and '1'.
這題題目給我們一個只包含 '0', '1' 的字串，
想請我們找到合法子字串的數量。
合法的定義是當子字串裡面的 1 數量大於等於 0 時，
此子字串稱作合法。
這題我原本想用 sliding window 來做，
但是不行，我舉個例子：
s = 100111
-> 考慮 index 0. 1 為合法子字串，繼續往右擴張
-> index 0, 1, 2 為非法字串，左邊界緊縮
-> index 2, 3 為合法子字串，繼續往右擴張
...
-> index 2, 3, 4, 5 為合法子字串，但看不到 index 0, 1, 2, 3, 4, 5 也是合法子字串
所以這題要固定 0 的數量，相當於解決了一個變數，
再來用 sliding window 推測，這樣就解決了。
C++程式碼：
