Leetcode 1513: Number of Substrings With Only 1s
Given a binary string s, return the number of substrings that consist entirely of ‘1’s. Since the result can be large, return the answer modulo (10^9 + 7).
Problem
Approach
Steps
Complexity
Input: The input consists of a binary string s, where each character is either '0' or '1'.
Example: s = "1010101"
Constraints:
• 1 <= s.length <= 10^5
• s[i] is either '0' or '1'.
Output: Return the number of substrings that contain only '1's modulo (10^9 + 7).
Example: 9
Constraints:
• Return the result modulo (10^9 + 7).
Goal: The goal is to calculate the total number of substrings consisting only of '1's. This can be done by grouping consecutive '1's together and applying the formula for the number of substrings from a sequence of length n: ( rac{n(n+1)}{2} ).
Steps:
• Step 1: Traverse the string to find groups of consecutive '1's.
• Step 2: For each group of consecutive '1's, calculate the number of substrings using the formula ( rac{n(n+1)}{2} ), where n is the length of the group.
• Step 3: Sum all the values from step 2 and take the result modulo (10^9 + 7).
Goal: The binary string must meet the constraints outlined in the input representation.
Steps:
• 1 <= s.length <= 10^5
• s[i] is either '0' or '1'.
Assumptions:
• The string contains at least one character.
• The string is composed only of '0' and '1'.
• Input: s = "1010101"
• Explanation: In this case, we can see that there are multiple occurrences of '1'. The valid substrings consist of individual '1's, pairs of '1's, and triplets of '1's, totaling 9 valid substrings.
• Input: s = "0001"
• Explanation: Only one substring consisting of '1' exists, so the output is 1.
Approach: The problem can be solved by iterating through the string and counting the number of consecutive '1's. For each group of '1's, we calculate the number of valid substrings using the formula ( rac{n(n+1)}{2} ).
Observations:
• The string can have multiple groups of consecutive '1's.
• We need to iterate through the string and calculate the number of substrings for each group of '1's.
Steps:
• Step 1: Iterate through the string to find sequences of consecutive '1's.
• Step 2: For each sequence, calculate the number of valid substrings using the formula ( rac{n(n+1)}{2} ).
• Step 3: Sum all these values and return the result modulo (10^9 + 7).
Empty Inputs:
• There is no need to handle empty inputs as the problem guarantees at least one character.
Large Inputs:
• Ensure that the solution efficiently handles strings with lengths up to 100,000 characters.
Special Values:
• Handle cases where the string consists only of '0's or only of '1's.
Constraints:
• The algorithm must run in O(n) time to handle large inputs efficiently.
int numSub(string s) {
long cnt = 0, mod = (int) 1e9 + 7;
long tmp = 0, n = s.size();
for(int i = 0; i < n; i++) {
if(s[i] == '1') {
tmp++;
}
if(s[i] == '0' || i == n - 1) {
cnt = (cnt + tmp * (tmp + 1) / 2) % mod;
tmp = 0;
}
}
return cnt;
}
1 : Function Definition
int numSub(string s) {
Defines the `numSub` function that takes a string `s` as input and calculates the number of substrings containing only '1' using a mathematical approach.
2 : Variable Initialization
long cnt = 0, mod = (int) 1e9 + 7;
Initializes `cnt` to 0, which will store the total number of valid substrings, and `mod` with the value (10^9 + 7) to take the result modulo this value.
3 : Variable Initialization
long tmp = 0, n = s.size();
Initializes `tmp` to 0, which will be used to count consecutive '1's, and `n` to the size of the string `s`.
4 : Loop Start
for(int i = 0; i < n; i++) {
Starts a loop that iterates through each character in the string `s`.
5 : Condition Check
if(s[i] == '1') {
Checks if the current character is '1'. If true, it increments the counter for consecutive '1's.
6 : Increment Counter
tmp++;
Increments the `tmp` variable, which keeps track of the number of consecutive '1's.
7 : Condition Check
if(s[i] == '0' || i == n - 1) {
Checks if the current character is '0' or if the loop has reached the last character in the string. This condition handles the end of a sequence of '1's or the end of the string.
8 : Calculate Valid Substrings
cnt = (cnt + tmp * (tmp + 1) / 2) % mod;
Calculates the number of valid substrings from the current sequence of consecutive '1's. This is done by adding the sum of the first `tmp` natural numbers, i.e., ( rac{tmp imes (tmp + 1)}{2} ), to `cnt`, and takes the result modulo `mod`.
9 : Reset Temporary Counter
tmp = 0;
Resets the `tmp` counter to 0, as the sequence of consecutive '1's has ended.
10 : Return Result
return cnt;
Returns the total count of valid substrings stored in `cnt`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) since we are iterating through the string once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we only need a constant amount of space to store intermediate variables.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus