Substring Parity
MediumPractice library · +20 XPstringsprefix sumsparity
Given a binary string S, find the number of substrings of S that have an equal number of 0s and 1s.
Input
The first line contains a binary string S.
Output
Print a single integer, the count of substrings with an equal number of 0s and 1s.
Constraints
1 <= |S| <= 200000, S consists only of characters '0' and '1'.
Time limit 1 s (native code; slower languages get more)Memory 256 MB16 hidden tests
Example 1
Input
01010
Output
6
Substrings are "01", "10", "01", "10", "0101", "1010". Total 6.
Example 2
Input
111
Output
0
No substrings have equal 0s and 1s. Total 0.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
01010
Example 2 input
111