[Algo Rhythm🕺💃] LeetCode - Number of Substrings With Only 1s

📚 Problem description

Given a binary string s (a string consisting only of '0' and '1's).

Return the number of substrings with all characters 1's.

Since the answer may be too large, return it modulo 10^9 + 7.

 

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

 

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

 

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

 

Example 4:

Input: s = "000"
Output: 0

 

Constraints:

• s[i] == '0' or s[i] == '1'

• 1 <= s.length <= 10^5

 

🎯 My code

import java.util.Arrays;

class Solution {
    public int numSub(String s) {
        int ans = 0;
        int n = s.length();        
        double[] arr = new double[n + 1];
        arr[0] = 0.0;
        
        for(int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if(ch == '0') {
                arr[i + 1] = 0.0;
            }
            if(ch == '1') {
                arr[i + 1] = arr[i] + 1.0;
            }
        }
        
        ans = (int)((Arrays.stream(arr).sum()) % (Math.pow(10.0, 9.0) + 7));
            
        return ans;
    }
}

 

🧐 Why I wrote that code

When I learned dynamic programming, professor said,

"The essential of dynamic programming is 'Do not repeat the same calculation.'."

 

With this in mind, I realized that I don't need to calculate the number of one 1, the number of two consecutive 1s, and more. That was repeating the same calculation.

 

To avoid the same calculation, I found the rule as below.

 

 

📖 What I learned

I reminded the essential of dynamic programming, 'Do not repeat the same calculation'.