MaximumBalances
SRM 784 · 2020-04-23 · by misof
Problem Statement
This problem is about strings that consist of left and right parentheses only: '(' and ')'.
Informally, a string is called balanced if each left parenthesis has a matching right parenthesis, as in a mathematical expression.
Formally:
- The empty string is a balanced string.
- If S is a balanced string, then '(' + S + ')' is a balanced string.
- If S and T are balanced strings, so is S + T.
- No other strings are balanced.
For example, strings "()", "(())", and "(()())()" are balanced while "(", ")(", and "(()))" are not.
The beauty of a string S is the number of non-empty contiguous substrings of S that are balanced. Two substrings are considered distinct if they begin and/or end at different positions in S.
Example: The beauty of the string "()(())" is 4, as shown below.
string: ()(())
balanced substrings: ()....
..(())
...().
()(())
You are given a
Constraints
- s will contain between 1 and 2,500 characters, inclusive.
- Each character of s will be '(' or ')'.
"(((("
Returns: 0
This is the only string we can produce: rearranging four left parentheses doesn't change anything. The beauty of this string is zero: there are no non-empty balanced substrings.
"(())" Returns: 3
We can rearrange these parentheses in several different ways, for example, "))((", "())(", "(())", or "()()". Among all the options the most beautiful one is the string "()()" with beauty 3.
")))())" Returns: 1
The input string is one of the most beautiful strings. There are also other strings with the same beauty: 1.
"))()()))(()" Returns: 10
"("
Returns: 0
Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MaximumBalances with a public method int solve(string s) · 73 test cases · 2 s / 256 MB per case