Number of Substrings With Only 1s - Video Solutions
Number of Substrings With Only 1s | 2 Ways | Dry Runs | Leetcode 1513 | codestorywithMIK
Number of Substrings With Only 1s - Video Solution
Watch 10 video solutions for Number of Substrings With Only 1s, a medium level problem involving Math, String. This walkthrough by codestorywithMIK has 4,440 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 109 + 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 <= 105s[i]is either'0'or'1'.
Approach Overview
Problem Overview: Given a binary string s, count how many substrings contain only the character '1'. Every contiguous block of ones contributes multiple valid substrings, so the task reduces to efficiently counting substrings formed inside these blocks.
Approach 1: Brute Force Substring Check (O(n^2) time, O(1) space)
Generate every possible substring and check whether it contains only '1'. Use two nested loops: the outer loop selects the start index and the inner loop extends the substring while characters remain '1'. Each time the extension still contains only ones, increment the count. The moment a '0' appears, stop extending that start index. This approach works but still explores up to O(n^2) substrings in the worst case (for example, a string of all ones), which becomes too slow for large inputs.
Approach 2: Consecutive Ones Counting and Arithmetic (O(n) time, O(1) space)
The key observation: if you have a consecutive run of k ones, the number of substrings made entirely of ones inside that run is k * (k + 1) / 2. For example, the block "111" produces substrings "1", "1", "1", "11", "11", and "111" — six total. Instead of checking substrings explicitly, iterate through the string once and maintain a counter for the current streak of consecutive ones. Each time you see '1', increase the streak and add it to the answer. When you encounter '0', reset the streak to zero.
This works because every new '1' extends all previous valid substrings ending at the previous index and also forms a new substring by itself. The algorithm performs a single pass through the string and uses constant memory. Since the result can be large, apply modulo 1e9 + 7. The reasoning relies on simple combinatorics from math and sequential processing of the string.
Recommended for interviews: The consecutive ones counting approach is what interviewers expect. It demonstrates the ability to recognize patterns in substring counting and convert them into a simple arithmetic formula. Mentioning the brute force idea first shows you understand the problem space, but moving quickly to the O(n) streak-counting method shows strong optimization skills.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Expansion | O(n^2) | O(1) | Useful for understanding substring enumeration or when constraints are very small |
| Consecutive Ones Counting + Arithmetic Formula | O(n) | O(1) | Best general solution; single pass counting of runs of ones |