Description

给定一个只包含0、1的字符串s，找出有相同数量0和1，且所有0和所有1都是组合在一起的子字符串数量。

例如“00110011”有6个子串具有相同数量的连续1和0：

“0011”，“01”，“1100”，“10”，“0011” 和 “01”，

子串“00110011”不是有效的，因为它的0和1没有组合在一起。

Input Format

字符串s，长度在1到50,000之间。

数据范围为$1～5×10^4$，如果使用$O(n​^2)$的算法，程序可能会超过每秒$10^8$次运算导致超时。

Output Format

满足要求的子串数量

10101​

4​

Source

基础百练 数组与字符串