Google | Onsite | Count submatricies with all 1s
3170

Question:
Write a function that given a binary string (consisting of 0s and 1s), returns the count of substrings with only 1s.

Example 1:

Input: "0011100110"
Output: 9

Example 2:

Input: "001111110"
Output: 21
Solution
public static int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int start = i; i < s.length() && s.charAt(i) == '1'; i++) {
            count += i - start + 1;
        }
    }
    return count;
}

Follow-up:
Write a function, that given a binary matrix, returns the count of submatrices with only 1s.

Example:

Intput:
[[1, 0, 1],
 [1, 1, 1]]

Output: 10
Comments (15)