Count Substrings with Equal 0s and 1s
Medium
Given a binary string (a string consisting only of '0's and '1's), count the number of substrings that contain an equal number of '0's and '1's and all 0's and all 1's inside the substring occur in groups of contiguous 0's or 1's.
Example 1
Input
[ "00110011" ]
Output
6
Explanation. There are 6 substrings that meet the criteria: '0011', '01', '1100', '10', '0011', '01'.
Example 2
Input
[ "10101" ]
Output
4
Explanation. There are 4 substrings that meet the criteria: '10', '01', '10', '01'.
Follow-up: Can this problem be solved in linear time and space? What is the importance of the substrings being contiguous in terms of algorithm complexity?
Constraints:
The length of the input string will be at least 1 and at most 1000. The string will consist only of digits '0' and '1'.
- Views
- 12