Solution Explanation

This problem asks to find the number of substrings containing only '1's in a given binary string. A naive approach would involve iterating through all possible substrings and checking each one, which would result in O(n^2) time complexity. However, a more efficient approach exists leveraging the fact that we're only interested in substrings of consecutive '1's.

Efficient Approach

The core idea is to count consecutive '1's and calculate the number of substrings formed by these consecutive '1's. If we have k consecutive '1's, the number of substrings consisting only of '1's is the sum of integers from 1 to k, which is k*(k+1)/2.

The algorithm iterates through the string:

1. Initialization: ans (total count of substrings) and cnt (count of consecutive '1's) are initialized to 0.
2. Iteration: For each character in the string:
   • If the character is '1', increment cnt.
   • If the character is '0', reset cnt to 0.
   • Add cnt to ans. This adds the number of substrings of '1's ending at the current position.
3. Modulo Operation: Finally, the result ans is taken modulo 10^9 + 7 to handle potential integer overflow.

Time Complexity Analysis:

The algorithm iterates through the string once, making its time complexity O(n), where n is the length of the string. This is significantly better than the naive O(n^2) approach.

Space Complexity Analysis:

The algorithm uses a constant amount of extra space to store ans and cnt, resulting in O(1) space complexity.

Code Examples (with detailed explanations):

The code examples provided in various languages implement this efficient algorithm. They are all structurally similar, differing only in syntax:

Python3:

class Solution:
    def numSub(self, s: str) -> int:
        ans = cnt = 0
        for c in s:
            if c == "1":
                cnt += 1
            else:
                cnt = 0
            ans += cnt  #Add the number of substrings ending at current position
        return ans % (10**9 + 7)

Java:

class Solution {
    public int numSub(String s) {
        final int mod = (int) 1e9 + 7;
        int ans = 0, cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            cnt = s.charAt(i) == '1' ? cnt + 1 : 0;
            ans = (ans + cnt) % mod;
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int numSub(string s) {
        int ans = 0, cnt = 0;
        const int mod = 1e9 + 7;
        for (char& c : s) {
            cnt = c == '1' ? cnt + 1 : 0;
            ans = (ans + cnt) % mod;
        }
        return ans;
    }
};

Go:

func numSub(s string) (ans int) {
	const mod = 1e9 + 7
	cnt := 0
	for _, c := range s {
		if c == '1' {
			cnt++
		} else {
			cnt = 0
		}
		ans = (ans + cnt) % mod
	}
	return
}

TypeScript:

function numSub(s: string): number {
    const mod = 10 ** 9 + 7;
    let ans = 0;
    let cnt = 0;
    for (const c of s) {
        cnt = c == '1' ? cnt + 1 : 0;
        ans = (ans + cnt) % mod;
    }
    return ans;
}

All these code snippets follow the same logic: iterating through the string, counting consecutive '1's, and accumulating the count of substrings. The modulo operation ensures the result stays within the specified range.