Counting Balanced Parenthesis Substrings
National Olympiad — National round (2023 season)
Submission name: brackets.cpp
Problem summary
Count nonempty contiguous balanced-parenthesis substrings.
Input
One string of( and).
Output
The number of valid nonempty substrings.
Constraints
1≤length≤200000.
Worked example
Input and output for the worked example discussed below.
Input
(())
Output
2
Solution analysis
- Match parentheses using a stack of opening indices. An unmatched closing position ends no valid substring.
- If closing index i matches opening p, ending[i]=1+ending[p−1]. The1 is the matched block itself; preceding valid substrings can concatenate with that block.
- For(()), the inner pair and the full outer block contribute one each, giving2. For()(), the final position ends two valid substrings: the last pair and the full concatenation. Sum all ending counts.
Why it works
Every valid substring ending at i starts at matching p or prepends a balanced substring ending at p−1. These cases are disjoint and exhaustive. Each substring has exactly one endpoint, so summing the recurrence counts it once.
Complexity: O(N) time and O(N) space. The answer needs long long.
Watch out. The empty string is not counted as an occurrence, as samples confirm. Count concatenations, not just matching pairs.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<string>
using namespace std;
// Every valid substring ending at i starts at matching p or prepends a balanced substring ending at p−1.
int main(){
string s;
cin>>s;
vector<int>openings;
vector<long long>ending(s.size(),0);
long long answer=0;
for(int i=0;i<int(s.size());i++){
if(s[i]=='('){
openings.push_back(i);
}
else if(!openings.empty()){
int p=openings.back();
openings.pop_back();
ending[i]=1+(p>0?ending[p-1]:0);
answer+=ending[i];
}
}
cout<<answer<<'\n';
}