Number of Substrings With Only 1s

Med

#1395Time: O(N^2), where N is the length of the string `s`. In the worst-case scenario (a string of all '1's), the inner loop runs approximately N times for each iteration of the outer loop.Space: O(1), as we only use a few variables to store the count and loop indices, regardless of the input size.

Patterns

Math

Data structures

String

Prompt

Given a binary string s, return the number of substrings with all characters 1's. Since the answer may be too large, return it modulo 10⁹ + 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.

Constraints:

1 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating all possible substrings of the input string and checking each one to see if it consists solely of '1's. We use two nested loops to define the start and end points of each substring.

Algorithm

Initialize a counter count to 0.
Use an outer loop to iterate through the string with index i from 0 to n-1, representing the start of a potential substring.
If s.charAt(i) is '0', continue to the next starting position.
If s.charAt(i) is '1', start an inner loop with index j from i to n-1.
Inside the inner loop, if s.charAt(j) is '1', it means the substring from i to j is valid. Increment count.
If s.charAt(j) is '0', break the inner loop as no more valid substrings can be formed starting from i.
After the loops complete, return count modulo 10^9 + 7.

Walkthrough

The algorithm iterates through every possible starting position i of a substring. For each starting position, it iterates through every possible ending position j. If the character at the starting position s[i] is '1', we then check subsequent characters. As long as we encounter '1's, each character s[j] helps form a new valid substring s[i...j]. We increment our total count for each such valid substring. If we encounter a '0', we know that no further substrings starting at i can be valid, so we break the inner loop and move to the next starting position i+1.

1class Solution {2    public int numSub(String s) {3        long count = 0;4        int n = s.length();5        int mod = 1_000_000_007;6 7        for (int i = 0; i < n; i++) {8            if (s.charAt(i) == '1') {9                for (int j = i; j < n; j++) {10                    if (s.charAt(j) == '1') {11                        count++;12                    } else {13                        break; // End of a sequence of 1s14                    }15                }16            }17        }18 19        return (int) (count % mod);20    }21}

Complexity

Time

O(N^2), where N is the length of the string `s`. In the worst-case scenario (a string of all '1's), the inner loop runs approximately N times for each iteration of the outer loop.

Space

O(1), as we only use a few variables to store the count and loop indices, regardless of the input size.

Trade-offs

Pros

Easy to understand and implement as it directly translates the problem definition.

Cons

Highly inefficient and will result in a 'Time Limit Exceeded' error for the given constraints (N up to 10^5).

A more efficient approach is to iterate through the string once and count the lengths of contiguous blocks of '1's. For a block of k consecutive '1's, the number of substrings it can form is the sum of integers from 1 to k, which is k * (k + 1) / 2. However, a simpler way to achieve the same result is to add the length of the current consecutive block of '1's to the total count at each step.

Algorithm

Initialize totalCount (for the final result) and currentCount (for the length of the current block of '1's) to 0.
Define the modulus mod = 10^9 + 7.
Iterate through the string s from left to right.
If the current character is '1', increment currentCount.
If the current character is '0', reset currentCount to 0, as the contiguous block of '1's is broken.
In every iteration, add the current value of currentCount to totalCount.
Perform the addition modulo mod to prevent overflow: totalCount = (totalCount + currentCount) % mod.
After the loop, totalCount will hold the final result.

Walkthrough

This method avoids nested loops by using a single pass. We maintain a variable, currentCount, to track the length of the current contiguous sequence of '1's. We iterate through the string. If the current character is '1', we increment currentCount. If it's a '0', the sequence is broken, so we reset currentCount to 0. At each step of the iteration, we add the value of currentCount to our totalCount. This works because a sequence of k ones adds k new substrings ending at the current position. For example, for '111', the counts added are 1 (for '1'), then 2 (for '1', '11' ending at the second '1'), then 3 (for '1', '11', '111' ending at the third '1'), summing to 1+2+3=6. All calculations are done modulo 10^9 + 7 to prevent overflow.

1class Solution {2    public int numSub(String s) {3        long totalCount = 0;4        long currentCount = 0;5        int mod = 1_000_000_007;6 7        for (int i = 0; i < s.length(); i++) {8            if (s.charAt(i) == '1') {9                currentCount++;10            } else {11                currentCount = 0;12            }13            totalCount = (totalCount + currentCount) % mod;14        }15 16        return (int) totalCount;17    }18}

Complexity

Time

O(N), where N is the length of the string `s`. We perform a single pass through the string.

Space

O(1), as we only use a constant amount of extra space for our counter variables.

Trade-offs

Pros

Extremely efficient and optimal in terms of time and space complexity.
Handles large inputs within the time limits.

Cons

The logic of adding currentCount at each step might require a moment of thought to understand its correctness compared to the more direct k*(k+1)/2 formula.

Solutions

Solution

1class Solution {2public:3  int numSub(string s) {4    int ans = 0, cnt = 0;5    const int mod = 1e9 + 7;6    for (char &c : s) {7      cnt = c == '1' ? cnt + 1 : 0;8      ans = (ans + cnt) % mod;9    }10    return ans;11  }12};

1class Solution:2    def numSub(self, s: str) -> int: ans = cnt = 0 for c in s: if c == "1": cnt += 1 else: cnt = 0 ans += cnt return ans % (10 ** 9 + 7)

1class Solution {2public3  int numSub(String s) {4    final int mod = (int)1 e9 + 7;5    int ans = 0, cnt = 0;6    for (int i = 0; i < s.length(); ++i) {7      cnt = s.charAt(i) == '1' ? cnt + 1 : 0;8      ans = (ans + cnt) % mod;9    }10    return ans;11  }12}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem