1513. Number of Substrings With Only 1s

[mah-shamim]

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.

[mah-shamim]

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) {
    $mod = 1000000007;
    $total = 0;
    $currentCount = 0;

    for ($i = 0; $i < strlen($s); $i++) {
        if ($s[$i] == '1') {
            $currentCount++;
        } else {
            // Calculate substrings for the current group of 1s
            $total = ($total + (int)($currentCount * ($currentCount + 1) / 2)) % $mod;
            $currentCount = 0;
        }
    }

    // Don't forget the last group
    $total = ($total + (int)($currentCount * ($currentCount + 1) / 2)) % $mod;

    return $total;
}

// 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)

[kovatz]

Thanks for solving the problem of "Number of Substrings With Only 1s"

[mah-shamim]

Thanks