Question
Count Balanced Parentheses Substrings
You are given a string s of length n consisting only of characters '(' and ')'. Your task is to count the number of substrings that form a balanced parentheses sequence.
A substring is considered balanced if:
- Every opening parenthesis has a corresponding closing parenthesis.
- The parentheses are properly nested.
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 string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression, consisting only of
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression, consisting only of
'(' and ')'.Output
Print a single integer — the number of substrings of KaTeX can only parse string typed expression that are balanced parentheses sequences.
Example
Input
6
(()())
Output
4
Explanation
Valid balanced substrings are:
() → from index 1 to 2
() → from index 3 to 4
()() → from index 1 to 4
(()()) → from index 0 to 5
Total = 4 substrings.
6
(()())
Output
4
Explanation
Valid balanced substrings are:
() → from index 1 to 2
() → from index 3 to 4
()() → from index 1 to 4
(()()) → from index 0 to 5
Total = 4 substrings.