Problem Breakdown
We are given a binary string s containing only ‘0’ and ‘1’. The goal is to count every possible substring that consists entirely of the character ‘1’. Since we need substrings (contiguous sequences), any contiguous block of consecutive ‘1’s contributes multiple valid substrings.
Inputs: A single string s.
Outputs: An integer representing the total count, modulo .
Constraints: String length up to , characters are strictly binary.
Implicit Constraints/Edge Cases:
- The result can exceed standard 32-bit integers (hence the modulo requirement).
- A string of all ‘0’s should return 0.
- We must handle large inputs efficiently ( is required, will Time Limit Exceed).
Intuition
A naive approach would be to iterate through every possible substring and check if it contains only ‘1’s. There are roughly substrings in a string of length . Checking each takes time proportional to its length, leading to an overall complexity around or optimized to . Given the constraint , this is far too slow.
Key Insight: Substrings containing only ‘1’s are formed exclusively within contiguous segments of ‘1’s separated by ‘0’s’. A single ‘0’ breaks a sequence and resets our count for that segment.
Consider a contiguous block (run) of ones: ... 1, 1, ..., 1 ....
- The last character contributes to the current run length as a new substring ending there.
- If we have a run of length , it contains substrings consisting only of ‘1’s (sum of integers from 1 to L).
Optimal Strategy: Instead of calculating the sum formula for each block, we can iterate through the string. Whenever we encounter a ‘1’, we increment our current run length counter and add that value directly to our total count. When we hit a ‘0’, we reset the run length counter to 0. This effectively calculates on the fly without needing separate arithmetic progression logic per block, keeping it simple and .
Approach
- Initialize
total_count = 0,current_run_length = 0. DefineMOD = 10^9 + 7. - Iterate through each character in string
s:- If the character is ‘1’: Increment
current_run_lengthby 1. Add this new length tototal_count. Apply modulo at each addition (or just once before return, though intermediate application prevents overflow logic issues if ported). - If the character is ‘0’: Reset
current_run_lengthto 0 because any substring crossing a ‘0’ contains non-‘1’s.
- If the character is ‘1’: Increment
- Return
total_count % MOD.
Complexity Analysis
- Time Complexity: , where is the length of string
s. We traverse the input exactly once with constant-time operations inside the loop. - Space Complexity: . We only use a few integer variables for counting and state tracking regardless of input size.
Solution
class Solution:
def numSub(self, s: str) -> int:
MOD = 10**9 + 7
total_count = 0
current_run_length = 0
# Iterate through each character in the binary string
for char in s:
if char == '1':
# Increment run length and add to total count.
# Each new '1' extends all previous valid substrings ending at this position
# plus creates a new single-character substring of itself.
current_run_length += 1
total_count = (total_count + current_run_length) % MOD
else:
# Reset run length when encountering '0'.
current_run_length = 0
return total_count
Edge Cases Handled
- All Zeros: The loop resets
current_run_lengthevery time, resulting in a final count of 0. Correct. - All Ones:
current_run_lengthincrements continuously; the sum accumulates correctly up to . Modulo ensures it fits requirements. - Single Character ‘1’: Loop runs once, adds 1 to total. Returns 1. Correct.
- Large Input (): The linear scan handles this within time limits; modulo arithmetic prevents