We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Substrings With Only 1s

Number: 1636

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary string s, the task is to count the number of contiguous substrings that consist only of the character '1'. Because the answer can be very large, we return the count modulo 10^9 + 7.

Key Insights

  • Instead of checking every substring (which is inefficient), notice that contiguous segments of '1's can be counted mathematically.
  • If a segment of '1's has length n, then the total number of substrings within that segment is given by n*(n+1)/2.
  • Iterate over the string, count consecutive '1's, and whenever a '0' is encountered or at the end, add the computed number of substrings from that segment to the answer.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), as only a few integer variables are used.

Solution

The solution involves a single pass through the string. We keep a counter for the current sequence of consecutive '1's. For every index:

  • If the character is '1', we increment the current count and add it to the result (since each new '1' extends all previous substrings ending at the previous '1's).
  • If the character is '0', we reset the count to 0. Finally, we return the result modulus 10^9 + 7. This method efficiently aggregates the substring counts without generating them explicitly.

Code Solutions

# Define the modulo constant
MOD = 10**9 + 7

def numSub(s: str) -> int:
    # Initialize variables for the current count of consecutive '1's and the result counter.
    count = 0
    result = 0
    
    # Iterate through each character in the string
    for char in s:
        if char == '1':
            # If the character is '1', increment the counter of consecutive '1's
            count += 1
            # Add the current count to the result as all substrings ending at this index are valid
            result = (result + count) % MOD
        else:
            # Reset count when a '0' is encountered
            count = 0
            
    return result

# Example usage:
if __name__ == "__main__":
    s = "0110111"
    print(numSub(s))  # Output should be 9
← Back to All Questions