Taro Logo

Number of Substrings With Only 1s

#1432 Most AskedMedium
34 views
Topics:
StringsArrays

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

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum length of the input string?
  2. Can the input string be empty or null?
  3. Does the string only contain '0' and '1' characters, or could there be other characters present?
  4. Should the return value be a 64-bit integer to handle potentially large results?
  5. If there are no substrings containing only '1's, should I return 0?

Brute Force Solution

Approach

The problem is counting how many groups of consecutive 1s we can find in a sequence. A brute force method checks every possible group to see if it consists only of 1s. We simply go through all combinations, counting the valid ones.

Here's how the algorithm would work step-by-step:

  1. Consider the first number in the sequence. Check if it's a 1. If it is, count it as a valid group.
  2. Then, consider the first two numbers together. Check if both are 1s. If so, count this group.
  3. Next, look at the first three numbers together. Check if they're all 1s. Count if they are.
  4. Continue expanding the group size from the beginning of the sequence until you reach the end.
  5. Now, shift the focus to the second number. Start by considering it individually.
  6. Repeat the process of expanding the group size, checking if all numbers are 1s, and counting the valid groups, starting from the second number.
  7. Keep shifting the starting position further down the sequence, repeating the group size expansion and validation process each time.
  8. Continue this process until you have checked every possible starting position and group size combination within the sequence.
  9. Finally, add up the counts of all the valid groups of consecutive 1s that you found during this exhaustive checking process.

Code Implementation

def number_of_substrings_with_only_ones_brute_force(input_string):
    number_of_substrings = 0

    # Iterate through all possible starting positions
    for start_index in range(len(input_string)):

        # Iterate through all possible substring lengths
        for end_index in range(start_index, len(input_string)):
            substring = input_string[start_index:end_index + 1]

            # Check if the substring contains only 1s
            is_valid = True

            # It's only necessary to check if the string is not ones
            for char in substring:
                if char != '1':
                    is_valid = False
                    break

            # Increment the count if the substring is valid
            if is_valid:
                number_of_substrings += 1

    return number_of_substrings

Big(O) Analysis

Time Complexity
O(n²) – The provided algorithm iterates through all possible substrings of the input string. The outer loop determines the starting position of the substring, which can be any of the n characters. The inner loop extends the substring from the starting position to the end of the string, with a maximum length of n. Thus, for each starting position, it iterates up to n times. The total number of operations is proportional to the sum of lengths of all possible substrings, which is n + (n-1) + (n-2) + ... + 1. This sum can be expressed as n*(n+1)/2, which simplifies to O(n²).
Space Complexity
O(1) – The provided solution iterates through substrings of the input string without using any auxiliary data structures like lists, hashmaps, or stacks to store intermediate results. It only uses a few constant space variables for indexing and counting. Therefore, the space used does not scale with the input string length N, but remains constant. Thus, the space complexity is O(1).

Optimal Solution

Approach

The most efficient way to count substrings of consecutive '1's is to realize that a sequence of '1's of a certain length contributes a specific number of substrings. We can count the lengths of these sequences and then calculate the number of substrings they contribute without individually checking each one.

Here's how the algorithm would work step-by-step:

  1. Go through the string one character at a time.
  2. Keep track of how many consecutive '1's you've seen so far. Start this count at zero at the beginning.
  3. If you see a '1', increase the count of consecutive ones.
  4. If you see a '0', this means the sequence of '1's has ended. Calculate how many substrings there were in this run of ones using a simple formula. For example, if there were three '1's in a row, there are six substrings of all ones: '1', '1', '1', '11', '11', '111'. A sequence of length n contains n * (n + 1) / 2 substrings.
  5. Add this number of substrings to the total count.
  6. Reset the counter back to zero because the sequence of '1's is broken.
  7. After going through the entire string, you'll have the total count of substrings that consist only of '1's.

Code Implementation

def number_of_substrings_with_ones(input_string):
    total_substrings = 0
    consecutive_ones = 0

    for character in input_string:
        if character == '1':
            consecutive_ones += 1

        else:
            # Calculate substrings from the previous run of ones.
            total_substrings += (consecutive_ones * (consecutive_ones + 1)) // 2

            # Reset the counter after encountering a zero.
            consecutive_ones = 0

    # Handle any trailing ones at the end of the string.
    total_substrings += (consecutive_ones * (consecutive_ones + 1)) // 2

    return total_substrings

Big(O) Analysis

Time Complexity
O(n) – The algorithm iterates through the input string of length n exactly once to count consecutive ones and calculate substring contributions. Inside the loop, the operations performed are constant time: incrementing a counter, calculating the number of substrings using a formula, and adding to a total. Since the loop dominates the execution time and runs once for each character in the string, the time complexity is directly proportional to n, the length of the string. Thus the time complexity is O(n).
Space Complexity
O(1) – The algorithm uses a constant amount of extra space. It only needs to store the current count of consecutive ones, which is a single integer variable. The space required for this variable does not depend on the input string's length, N. Therefore, the auxiliary space complexity is constant.

Edge Cases

Null or empty input string
How to Handle:
Return 0 immediately as there are no substrings to count.
String contains no '1' characters
How to Handle:
Return 0 because no substring of only '1's exists.
String of length 1 containing '1'
How to Handle:
Return 1, as there is exactly one valid substring of length 1.
String with very long sequence of consecutive '1's (potential overflow)
How to Handle:
Use a 64-bit integer type (long in Java/C++, int64_t in C) to avoid integer overflow when calculating the number of substrings.
String with mixed '0's and '1's, but only single '1's separated by '0's
How to Handle:
Count each '1' individually, adding 1 for each occurrence to the total count.
String containing only '1's of maximum allowed length
How to Handle:
Ensure the calculation of substrings still completes without overflow or performance issues.
String with very short sequences of '1's interleaved with many '0's
How to Handle:
The algorithm should efficiently handle the alternating '0's and short '1' sequences without excessive computation.
Extremely long input string (approaching memory limits)
How to Handle:
Use an iterative approach rather than recursion to minimize memory usage.
0/1916 completed