Problem Description

You are given a binary string s that consists only of characters '0' and '1'. Your task is to count the total number of substrings that contain only '1' characters.

For example, if you have a string "0110111", you need to find all possible substrings that are made up entirely of '1's. In this case:

• From the first group "11": you can form substrings "1", "1", and "11" (total: 3)
• From the second group "111": you can form substrings "1", "1", "1", "11", "11", and "111" (total: 6)
• Total count: 3 + 6 = 9

The key insight is that for a consecutive sequence of n ones, the number of valid substrings is n * (n + 1) / 2. This is because:

• You have n substrings of length 1
• You have n-1 substrings of length 2
• You have n-2 substrings of length 3
• And so on...
• Which sums to n + (n-1) + (n-2) + ... + 1 = n * (n + 1) / 2

The solution iterates through the string character by character. It maintains a counter cnt that tracks the current length of consecutive '1's. For each '1' encountered, it increments the counter and adds the counter value to the answer. This works because at each position ending with '1', the number of valid substrings ending at that position equals the length of the current consecutive sequence of '1's.

Since the answer can be very large, you need to return the result modulo 10^9 + 7.

Intuition

When we see a problem asking for counting substrings with a specific property, we should think about how substrings are formed and counted efficiently.

Let's start with a simple observation: if we have a sequence of consecutive '1's, like "111", how many valid substrings can we form? We can pick:

• Any single '1': positions 0, 1, 2 → 3 substrings
• Any two consecutive '1's: positions (0,1), (1,2) → 2 substrings
• All three '1's: positions (0,1,2) → 1 substring
• Total: 3 + 2 + 1 = 6 substrings

This follows the pattern n + (n-1) + ... + 1 = n*(n+1)/2 for a sequence of length n.

But wait - there's a more elegant way to think about this! Instead of finding each group of consecutive '1's and applying the formula, we can count incrementally as we traverse the string.

The key insight: when we're at position i and it's a '1', how many valid substrings end at this position? The answer is exactly the number of consecutive '1's we've seen so far (including the current one). Why? Because each valid substring ending at position i must start from some position within the current consecutive sequence of '1's.

For example, in "0111":

• At index 1 (first '1'): 1 substring ends here: "1"
• At index 2 (second '1'): 2 substrings end here: "1" and "11"
• At index 3 (third '1'): 3 substrings end here: "1", "11", and "111"
• Total: 1 + 2 + 3 = 6

This naturally gives us the same result as the formula 3*(3+1)/2 = 6, but we compute it incrementally! We just maintain a counter that tracks consecutive '1's, reset it when we see a '0', and keep adding the counter value to our answer. This approach is both intuitive and efficient with O(n) time and O(1) space.

Learn more about Math patterns.

Solution Approach

The implementation uses a simple linear scan with two variables to solve the problem efficiently:

1. Initialize two variables:

   • ans: Accumulates the total count of valid substrings
   • cnt: Tracks the length of the current consecutive sequence of '1's

2. Iterate through each character in the string:

   for c in s:

3. For each character, apply the counting logic:

   • If the character is '1':

     if c == "1":
         cnt += 1

     Increment the counter by 1, extending the current sequence of consecutive '1's.

   • If the character is '0':

     else:
         cnt = 0

     Reset the counter to 0, as the consecutive sequence is broken.

4. Add the counter value to the answer:

   ans += cnt

   This is the crucial step - we add cnt to our answer after processing each character. When cnt is non-zero (we're in a sequence of '1's), this adds the number of valid substrings ending at the current position.

5. Return the result modulo 10^9 + 7:

   return ans % (10**9 + 7)

Why this works:

• When we encounter a '1' and cnt becomes k, it means there are exactly k valid substrings ending at this position (substrings of length 1, 2, ..., k starting from different positions in the current consecutive sequence)
• When we encounter a '0', cnt becomes 0, so we add 0 to the answer (no valid substrings end at a '0')
• The cumulative sum naturally gives us the total count of all valid substrings

Time Complexity: O(n) where n is the length of the string - we traverse the string once.

Space Complexity: O(1) - we only use two integer variables regardless of input size.

Example Walkthrough

Let's walk through the solution with the string s = "01101".

We'll track two variables:

• cnt: counts consecutive '1's
• ans: accumulates total valid substrings

Step-by-step process:

Final answer: 4

Let's verify by listing all valid substrings:

• From indices 1-2: "1" (at index 1), "1" (at index 2), "11" (indices 1-2) → 3 substrings
• From index 4: "1" (at index 4) → 1 substring
• Total: 3 + 1 = 4 ✓

The key insight is that when cnt = k, there are exactly k valid substrings ending at the current position:

• When cnt = 1: one substring of length 1
• When cnt = 2: one substring of length 2 and one of length 1
• When cnt = 3: one substring of length 3, one of length 2, and one of length 1
• And so on...

This incremental counting naturally accumulates to the same result as counting each group separately using the formula n*(n+1)/2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the string s. The algorithm iterates through each character in the string exactly once, performing constant-time operations (comparison, addition, modulo) for each character.

Space Complexity: O(1). The algorithm uses only a fixed amount of extra space regardless of the input size. It maintains three variables (ans, cnt, and c) which don't scale with the input size. The space used for the input string itself is not counted as auxiliary space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Apply the Modulo Operation

One of the most common mistakes is forgetting to apply the modulo operation or applying it incorrectly. The problem explicitly states that the answer should be returned modulo 10^9 + 7 to handle large numbers.

Incorrect Implementation:

def numSub(self, s: str) -> int:
    total_count = 0
    consecutive_ones = 0
  
    for char in s:
        if char == "1":
            consecutive_ones += 1
            total_count += consecutive_ones
        else:
            consecutive_ones = 0
  
    return total_count  # Missing modulo operation!

Why this fails: For very long strings with many '1's, the result can exceed the integer limits in some systems or expected output format, causing incorrect results or runtime errors.

Correct Solution:

def numSub(self, s: str) -> int:
    MOD = 10**9 + 7
    total_count = 0
    consecutive_ones = 0
  
    for char in s:
        if char == "1":
            consecutive_ones += 1
            total_count += consecutive_ones
        else:
            consecutive_ones = 0
  
    return total_count % MOD  # Apply modulo at the end

2. Integer Overflow in Intermediate Calculations

While Python handles large integers automatically, in other languages or when optimizing, you might try to use the formula n * (n + 1) / 2 directly for each group of consecutive '1's. This can cause overflow issues.

Potentially Problematic Approach:

def numSub(self, s: str) -> int:
    MOD = 10**9 + 7
    total_count = 0
    consecutive_ones = 0
  
    for i, char in enumerate(s):
        if char == "1":
            consecutive_ones += 1
            # Check if next character is '0' or end of string
            if i == len(s) - 1 or s[i + 1] == "0":
                # Using formula directly - can cause overflow in other languages
                total_count += (consecutive_ones * (consecutive_ones + 1)) // 2
                consecutive_ones = 0
      
    return total_count % MOD

Better Solution (with intermediate modulo):

def numSub(self, s: str) -> int:
    MOD = 10**9 + 7
    total_count = 0
    consecutive_ones = 0
  
    for char in s:
        if char == "1":
            consecutive_ones += 1
            # Apply modulo during accumulation to prevent overflow
            total_count = (total_count + consecutive_ones) % MOD
        else:
            consecutive_ones = 0
  
    return total_count

3. Misunderstanding the Counting Logic

Some might incorrectly think they need to count each group of '1's separately and then apply the formula, leading to more complex and error-prone code.

Overcomplicated Approach:

def numSub(self, s: str) -> int:
    MOD = 10**9 + 7
    groups = []
    i = 0
  
    # Find all groups of consecutive '1's
    while i < len(s):
        if s[i] == "1":
            j = i
            while j < len(s) and s[j] == "1":
                j += 1
            groups.append(j - i)
            i = j
        else:
            i += 1
  
    # Calculate sum for each group
    total = 0
    for length in groups:
        total += (length * (length + 1)) // 2
  
    return total % MOD

Why the simple approach is better: The incremental counting method is more elegant, requires less code, and naturally handles all cases without needing to explicitly identify groups or handle edge cases separately. It's also more memory-efficient as it doesn't store intermediate group information.