Question
Number of Balanced Binary Substrings
You are given a binary string of length KaTeX can only parse string typed expression, consisting only of characters KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. A substring is called balanced if it contains an equal number of KaTeX can only parse string typed expressions and KaTeX can only parse string typed expressions.
Your task is to count the total number of balanced substrings in the given string.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the length of the string.
The second line contains a binary string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression, consisting only of KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
The second line contains a binary string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression, consisting only of KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Output
Print a single integer — the number of balanced substrings of KaTeX can only parse string typed expression.
Example
Input
6
010011
Output
6
Explanation
Balanced substrings are:
(0, 1) → "01"
(0, 5) → "010011"
(1, 2) → "10"
(1, 4) → "1001"
(2, 5) → "0011"
(3, 4) → "01"
Total = 6 balanced substrings.
6
010011
Output
6
Explanation
Balanced substrings are:
(0, 1) → "01"
(0, 5) → "010011"
(1, 2) → "10"
(1, 4) → "1001"
(2, 5) → "0011"
(3, 4) → "01"
Total = 6 balanced substrings.