Welcome to Subscribe On Youtube

3234. Count the Number of Substrings With Dominant Ones

Description

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'.

Solutions

Solution 1

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public int numberOfSubstrings(String s) {
          int n = s.length();
          int[] nxt = new int[n + 1];
          nxt[n] = n;
          for (int i = n - 1; i >= 0; --i) {
              nxt[i] = nxt[i + 1];
              if (s.charAt(i) == '0') {
                  nxt[i] = i;
              }
          }
          int ans = 0;
          for (int i = 0; i < n; ++i) {
              int cnt0 = s.charAt(i) == '0' ? 1 : 0;
              int j = i;
              while (j < n && 1L * cnt0 * cnt0 <= n) {
                  int cnt1 = nxt[j + 1] - i - cnt0;
                  if (cnt1 >= cnt0 * cnt0) {
                      ans += Math.min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
                  }
                  j = nxt[j + 1];
                  ++cnt0;
              }
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      int numberOfSubstrings(string s) {
          int n = s.size();
          vector<int> nxt(n + 1);
          nxt[n] = n;
          for (int i = n - 1; i >= 0; --i) {
              nxt[i] = nxt[i + 1];
              if (s[i] == '0') {
                  nxt[i] = i;
              }
          }
          int ans = 0;
          for (int i = 0; i < n; ++i) {
              int cnt0 = s[i] == '0' ? 1 : 0;
              int j = i;
              while (j < n && 1LL * cnt0 * cnt0 <= n) {
                  int cnt1 = nxt[j + 1] - i - cnt0;
                  if (cnt1 >= cnt0 * cnt0) {
                      ans += min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
                  }
                  j = nxt[j + 1];
                  ++cnt0;
              }
          }
          return ans;
      }
  };
  
  

• class Solution:
      def numberOfSubstrings(self, s: str) -> int:
          n = len(s)
          nxt = [n] * (n + 1)
          for i in range(n - 1, -1, -1):
              nxt[i] = nxt[i + 1]
              if s[i] == "0":
                  nxt[i] = i
          ans = 0
          for i in range(n):
              cnt0 = int(s[i] == "0")
              j = i
              while j < n and cnt0 * cnt0 <= n:
                  cnt1 = (nxt[j + 1] - i) - cnt0
                  if cnt1 >= cnt0 * cnt0:
                      ans += min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1)
                  j = nxt[j + 1]
                  cnt0 += 1
          return ans
  
  

• func numberOfSubstrings(s string) int {
  	n := len(s)
  	nxt := make([]int, n+1)
  	nxt[n] = n
  	for i := n - 1; i >= 0; i-- {
  		nxt[i] = nxt[i+1]
  		if s[i] == '0' {
  			nxt[i] = i
  		}
  	}
  	ans := 0
  	for i := 0; i < n; i++ {
  		cnt0 := 0
  		if s[i] == '0' {
  			cnt0 = 1
  		}
  		j := i
  		for j < n && int64(cnt0*cnt0) <= int64(n) {
  			cnt1 := nxt[j+1] - i - cnt0
  			if cnt1 >= cnt0*cnt0 {
  				ans += min(nxt[j+1]-j, cnt1-cnt0*cnt0+1)
  			}
  			j = nxt[j+1]
  			cnt0++
  		}
  	}
  	return ans
  }
  
  

• function numberOfSubstrings(s: string): number {
      const n = s.length;
      const nxt: number[] = Array(n + 1).fill(0);
      nxt[n] = n;
      for (let i = n - 1; i >= 0; --i) {
          nxt[i] = nxt[i + 1];
          if (s[i] === '0') {
              nxt[i] = i;
          }
      }
      let ans = 0;
      for (let i = 0; i < n; ++i) {
          let cnt0 = s[i] === '0' ? 1 : 0;
          let j = i;
          while (j < n && cnt0 * cnt0 <= n) {
              const cnt1 = nxt[j + 1] - i - cnt0;
              if (cnt1 >= cnt0 * cnt0) {
                  ans += Math.min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
              }
              j = nxt[j + 1];
              ++cnt0;
          }
      }
      return ans;
  }
  
  

• impl Solution {
      pub fn number_of_substrings(s: String) -> i32 {
          let n = s.len();
          let mut nxt = vec![n; n + 1];
  
          for i in (0..n).rev() {
              nxt[i] = nxt[i + 1];
              if &s[i..i + 1] == "0" {
                  nxt[i] = i;
              }
          }
  
          let mut ans = 0;
          for i in 0..n {
              let mut cnt0 = if &s[i..i + 1] == "0" { 1 } else { 0 };
              let mut j = i;
              while j < n && (cnt0 * cnt0) as i64 <= n as i64 {
                  let cnt1 = nxt[j + 1] - i - cnt0;
                  if cnt1 >= (cnt0 * cnt0) {
                      ans += std::cmp::min(nxt[j + 1] - j, cnt1 - cnt0 * cnt0 + 1);
                  }
                  j = nxt[j + 1];
                  cnt0 += 1;
              }
          }
  
          ans as i32
      }
  }
  
  

All Problems

All Solutions