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'.This approach involves counting the number of consecutive 1s in segments and using arithmetic calculations to determine the count of all substrings of 1s within those segments. For a segment with k consecutive 1s, the number of substrings is given by k*(k+1)/2. We iterate through the string to find such segments and compute the count accordingly, taking care to apply modulo operation to handle large numbers.
The C solution traverses each character in the string, checking for consecutive '1's. Upon hitting a '0', or at the end of the string, it calculates the number of substrings for the current count of consecutive '1's and resets the counter. The modulo operation ensures that the result stays within the bounds of standard integer representation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) as we traverse the string once.
Space Complexity: O(1) as only a fixed number of extra variables are used.
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Number of Substrings With Only 1s with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor