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 <= 105s[i] is either '0' or '1'.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:
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:
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_substringsThe 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:
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| Case | How to Handle |
|---|---|
| Null or empty input string | Return 0 immediately as there are no substrings to count. |
| String contains no '1' characters | Return 0 because no substring of only '1's exists. |
| String of length 1 containing '1' | Return 1, as there is exactly one valid substring of length 1. |
| String with very long sequence of consecutive '1's (potential overflow) | 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 | Count each '1' individually, adding 1 for each occurrence to the total count. |
| String containing only '1's of maximum allowed length | 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 | The algorithm should efficiently handle the alternating '0's and short '1' sequences without excessive computation. |
| Extremely long input string (approaching memory limits) | Use an iterative approach rather than recursion to minimize memory usage. |