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 String s. You can rearrange the characters of s arbitrarily (but you cannot add, remove, or replace characters). Calculate and return the beauty of the most beautiful string you can produce.
Definition
- Class:
- MaximumBalances
- Method:
- solve
- Parameters:
- String
- Returns:
- int
- Method signature:
- int solve(String s)
- (be sure your method is public)
Constraints
- s will contain between 1 and 2,500 characters, inclusive.
- Each character of s will be '(' or ')'.
Examples
"(((("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