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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Substrings With Only 1s

Difficulty: Medium

Problem Description

Given a binary string s, return the number of substrings with all characters being '1's. Since the answer may be too large, return it modulo 10^9 + 7.

Key Insights

  • Each contiguous segment of '1's contributes to multiple substrings.
  • For a segment of length n consisting of '1's, the number of substrings is given by the formula n * (n + 1) / 2.
  • The solution requires iterating through the string and counting segments of '1's while summing their contributions.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will iterate through the binary string while maintaining a count of consecutive '1's. Whenever we encounter a '0', we will compute the number of substrings contributed by the counted '1's using the formula n * (n + 1) / 2 and reset the counter. Finally, we will return the total count of substrings modulo 10^9 + 7.

Code Solutions

def countBinarySubstrings(s: str) -> int:
    mod = 10**9 + 7
    count = 0
    current_count = 0
    
    for char in s:
        if char == '1':
            current_count += 1
        else:
            count += (current_count * (current_count + 1)) // 2
            current_count = 0
    
    count += (current_count * (current_count + 1)) // 2
    return count % mod
← Back to All Questions