1513. Number of Substrings With Only 1s

1513. Number of Substrings With Only 1s

Difficulty: Medium

Topics: Math, String, Weekly Contest 197

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 10⁹ + 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 <= 10⁵
• s[i] is either '0' or '1'.

Hint:

1. Count number of 1s in each consecutive-1 group. For a group with n consecutive 1s, the total contribution of it to the final answer is(n + 1) * n // 2.

Solution:

We need to count all substrings that contain only '1's in a binary string.

Approach:

The key insight is that for a contiguous group of n '1's:

• The number of substrings within that group is n*(n+1)/2
• For example, "111" has 6 substrings: "1", "1", "1", "11", "11", "111"

So we can:

1. Find all contiguous groups of '1's
2. For each group of length n, calculate n*(n+1)/2
3. Sum all these values

Let's implement this solution in PHP: 1513. Number of Substrings With Only 1s

<?php
/**
 * @param String $s
 * @return Integer
 */
function numSub($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo numSub("0110111") . "\n";  // Output: 9
echo numSub("101") . "\n";      // Output: 2
echo numSub("111111") . "\n";   // Output: 21
?>

Explanation:

1. Initialization: I set up variables to track the total count and the current streak of '1's.

2. Iterate through the string: For each character:

   • If it's '1', I increment the current streak counter
   • If it's '0', I calculate the number of substrings for the current streak using the formula n*(n+1)/2, add it to the total, and reset the streak counter

3. Handle the final group: After the loop, I check if there's a remaining streak of '1's and include it in the total.

4. Modulo operation: Since the result can be very large, I use modulo 10^9+7 at each addition step.

Time Complexity: O(n) where n is the length of the string

Space Complexity: O(1)

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub