Copy of Copy of Copy of Template

Problem Statement

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.

i	j	s[i..j]	Number of Zeros	Number of Ones
3	3	1	0	1
4	4	1	0	1
2	3	01	1	1
3	4	11	0	2
2	4	011	1	2

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.

i	j	s[i..j]	Number of Zeros	Number of Ones
1	1	0	1	0
4	4	0	1	0
1	4	0110	2	2
0	4	10110	2	3
1	5	01101	2	3

Constraints:

• 1 <= s.length <= 4 * 104

• s consists only of characters '0' and '1'.

Intuition

Approach

Try to do a prefix sum find of approach

Starting from i -> Count number of substrings possible from that point
Check the condition, If we can incorporate more,
Let say
11110
Here we can take one more zero, So shift j pointer ahead, 
To add that substring to answer

Similarly others

Links

https://leetcode.com/problems/count-the-number-of-substrings-with-dominant-ones/

Video Links

https://www.youtube.com/watch?v=hcGvofpRBg0&t=1030s&ab_channel=AbhinavAwasthi

Approach 1:

C++

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        int ans = 0;
        vector<int> pref(n,0);
        for(int i=0; i<s.size(); i++){
            if(s[i] == '1'){
                pref[i] = 1;
            }
        }
        for(int i=1; i<s.size(); i++){
            pref[i] = pref[i] + pref[i-1];
        }
     
        for(int i=0; i<s.size(); i++){
            
            for(int j=i; j<s.size(); j++){
                int ones = pref[j];
                if(i!=0) ones -= pref[i-1];
                int zeros = (j-i+1) - ones;

                if(zeros*zeros > ones){
                    j += (zeros*zeros - ones -1);
                }
                if(zeros*zeros <= ones){
                    ans ++;

                    if(zeros*zeros < ones){
                        int diff = sqrt(ones) - zeros;

                        if(j+diff >= n)
                            ans += (n-j-1);
                        else{
                            ans += diff;
                        }

                        j = j+diff;
                    }
                }
            }
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems