1513. Number of Substrings With Only 1s

MediumMathString
Leetcode Link

Problem Description

The problem requires us to find and count the number of substrings within a given binary string s that consist entirely of the character '1'. For example, in the string "0110111", there are several such substrings: "1", "11", "111", "11", "1", and each of them should be counted. The challenge here is to do this efficiently and to deal with potentially very large numbers, the counts need to be returned modulo 10^9 + 7, which is a large prime number commonly used to prevent integer overflow issues in competitive programming.

Intuition

The intuition behind the solution is based on the observation that for a sequence of '1's of length n, there are exactly n * (n + 1) / 2 substrings that can be formed, all of which consist solely of '1's. This is because each additional '1' potentially adds as many new substrings as its position in the sequence (first '1' adds 1 substring, second '1' adds 2 substrings, and so on). So, we are essentially counting the lengths of continuous sequences of '1's and calculating the number of substrings for each sequence.

The solution involves iterating through the string and using a counter variable cnt to keep track of the length of a consecutive sequence of '1's. When we encounter a '1', we increment cnt. If we encounter a '0', we reset cnt to zero, because it breaks the sequence of '1's. After each step, regardless of whether we're continuing a sequence or ending one, we add the current value of cnt to ans, which accumulates the total number of substrings of '1's we've seen so far.

Finally, since the answer could be a very large number, we return the total count modulo 10^9 + 7 as instructed by the problem description.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following uses divide and conquer strategy?

Solution Approach

The implementation of the solution is relatively straightforward with no need for complex data structures; the only variable that holds state during iteration is cnt, which counts the length of consecutive '1's. With every step forward in the string, the algorithm performs the following actions:

  1. Check the current character (c) of the string.
  2. If c is '1', increment the cnt variable: this increases the length of the current sequence of '1's by one.
  3. If c is not '1' (in this case, it could only be '0' since it's a binary string), reset cnt to zero. This indicates the end of the current sequence of '1's and resets the count for the next sequence.
  4. After updating cnt, add its current value to ans. This step accumulates the total number of valid substrings formed by the sequences of '1's encountered so far.

This process works because each time a '1' is encountered and cnt is incremented, it effectively counts all the new substrings that could end with this '1'. If you have a sequence of length n, then adding one more '1' to the sequence adds n + 1 substrings: all the previous substrings plus a new substring that includes the entire sequence.

The use of the modulo operation % (10**9 + 7) ensures that we handle the possibility of very large outputs, preventing integer overflow and keeping the result within the limits of the problem's constraints.

No additional data structures are required, and the pattern used in this algorithm is commonly known as a single pass or linear scan, as it requires only one iteration through the input string to compute the result.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Let's consider a small example binary string s = "11011". Here's how we would apply the solution approach to this input:

  1. Initialize cnt = 0 (to count the consecutive '1's) and ans = 0 (to accumulate the total number of substrings).

  2. Start iterating over the string s from left to right.

    • Character s[0] is '1':
      • Increment cnt to 1. Current substrings are: "1".
      • Add cnt to ans: ans += 1, hence ans = 0 + 1 = 1.
    • Character s[1] is '1':
      • Increment cnt to 2. Current substrings are: "1", "11".
      • Add cnt to ans: ans += 2, hence ans = 1 + 2 = 3.

  3. The next character s[2] is '0', which interrupts the sequence of '1's:

    • Reset cnt to 0.
    • ans remains unchanged.

  4. Continue iteration.

    • Character s[3] is '1':
      • Increment cnt to 1. Current substrings are: "1".
      • Add cnt to ans: ans += 1, hence ans = 3 + 1 = 4.
    • Character s[4] is '1':
      • Increment cnt to 2. Current substrings are: "1", "11".
      • Add cnt to ans: ans += 2, hence ans = 4 + 2 = 6.

  5. At this point, we have finished iterating over the entire string. The total count of substrings consisting only of '1's is stored in ans, which equals 6.

  6. Return ans % (10^9 + 7) to adhere to the problem constraints. Since 6 is well below the modulo, the final result is simply 6.

As we can see from the example, the algorithm correctly counts the individual substrings of '1's and sums them up. It counts "11" at the beginning as 2 substrings, resets the count after the '0', and then counts "1" and "11" again, adding up to a total of 6 substrings consisting of '1's.

Solution Implementation

1class Solution:
2    def numSub(self, s: str) -> int:
3        # Initialize the answer and a temporary counter for consecutive "1"s
4        total_substrings = consecutive_ones_count = 0
5      
6        # Iterate through each character in the string
7        for char in s:
8            # If the character is "1", increment the consecutive "1"s counter
9            if char == "1":
10                consecutive_ones_count += 1
11                # Add the current count of consecutive "1"s to the total substrings.
12                # Each time we encounter a "1", it forms a substring with all the consecutive "1"s before it.
13                total_substrings += consecutive_ones_count
14            # If the character is not "1", reset the consecutive "1"s counter to 0
15            else:
16                consecutive_ones_count = 0
17          
18        # Return the total number of substrings, modulo 10^9 + 7
19        return total_substrings % (10**9 + 7)
20
1class Solution {
2    // This method counts the number of substrings that contains only the character '1'
3    public int numSub(String s) {
4        final int MODULO = (int) 1e9 + 7; // Define a constant for modulo operation
5        int countSubstrings = 0; // Store the count of valid substrings
6        int consecutiveOnes = 0; // Counter for consecutive '1's
7
8        // Iterate through the string character by character
9        for (int i = 0; i < s.length(); ++i) {
10            // If the current character is '1', increment the consecutive ones counter
11            // Otherwise, reset it to zero since we're only interested in consecutive '1's
12            consecutiveOnes = s.charAt(i) == '1' ? consecutiveOnes + 1 : 0;
13
14            // Add the current count of consecutive '1's to countSubstrings
15            // This works because for each new '1' character, it forms a new substring
16            // ending at this character that has not been counted yet
17            countSubstrings = (countSubstrings + consecutiveOnes) % MODULO;
18        }
19      
20        // Return the total number of substrings found, modulo the defined constant
21        return countSubstrings;
22    }
23}
24
1class Solution {
2public:
3    // Function to count the number of substrings containing only '1's
4    int numSub(string s) {
5        long long answer = 0; // Initialize the answer to 0
6        int count = 0; // Initialize a counter for consecutive '1's
7        const int MODULUS = 1e9 + 7; // Define the modulus value for preventing integer overflow
8      
9        // Iterate over each character in the input string
10        for (char& character : s) {
11            // If the current character is '1', increase the count of consecutive '1's
12            // Otherwise, reset the count to 0
13            count = character == '1' ? count + 1 : 0;
14          
15            // Add the current count to the answer. This works because for each '1' found,
16            // it contributes to that many substrings ending at that point (e.g., "111" has
17            // substrings "1", "11", and "111" ending at the last character).
18            // Apply modulus operation to keep the number within bounds and handle overflow
19            answer = (answer + count) % MODULUS;
20        }
21      
22        // Return the final count of substrings
23        return static_cast<int>(answer); // Cast the long long answer to int before returning
24    }
25};
26
1function numSub(sequence: string): number {
2    // Define the modulus value to keep the result within integer limits
3    const modulus = 10 ** 9 + 7;
4  
5    // Initialize the answer to be returned
6    let answer = 0;
7  
8    // Counter for the consecutive '1's
9    let count = 0;
10  
11    // Iterate through each character in the string
12    for (const char of sequence) {
13        // If the character is '1', increase count, otherwise reset count to 0
14        count = (char === '1') ? count + 1 : 0;
15      
16        // Add the current count to the answer and apply modulus to prevent overflow
17        answer = (answer + count) % modulus;
18    }
19  
20    // Return the computed answer
21    return answer;
22}
23
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

The code provided counts the number of substrings of contiguous '1's in a given string s. The time complexity and space complexity of the algorithm are analyzed below.

Time Complexity

The algorithm goes through each character of the input string s exactly once. During this process, it performs constant time operations such as checking if a character is '1' or '0', incrementing the cnt variable, and adding the value of cnt to ans. Because these operations do not depend on the size of the string and are repeated for each character, the time complexity is directly proportional to the length of the string. Therefore, the time complexity is O(n), where n is the length of the input string s.

Space Complexity

The space used by the algorithm includes a fixed number of integer variables ans and cnt, which do not scale with the size of the input string. As a result, the algorithm uses a constant amount of additional space, resulting in a space complexity of O(1), indicating that it is independent of the input size.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫