Number of Substrings with All Zeroes

2021-07-11 208 words One minute

Contents

Problem Description

Given a string str containing only 0 or 1, please return the number of substrings that consist of 0.

1 <= |str| <= 30000

Example

Example 1:

Input:
"00010011"
Output:
9
Explanation:
There are 5 substrings of "0",
There are 3 substrings of "00",
There is 1 substring of "000".
So return 9

Example 2:

Input:
"010010"
Output:
5

Solution

Solution 1 - Two Pointers

"000" =>
1 * "000" + 2 * "00" + 3 * "0" =>
len("000") + len("00") + len("0") = 6

n个0的string =>
n * (n + 1) / 2 个全0的substring

public class Solution {
    /**
     * @param str: the string
     * @return: the number of substrings 
     */
    public int stringCount(String str) {
        int ret = 0;
        for (int i = 0; i < str.length(); ++i) {
            if (str.charAt(i) != '0') {
                continue;
            }
            if (i > 0 && str.charAt(i) == str.charAt(i - 1)) {
                continue;
            }

            int j = i;
            while (j < str.length() && str.charAt(j) == '0') {
                j++;
            }
            ret += (j - i) * (j - i + 1) / 2;
        }
        return ret;
    }
}