Minimum Bracket Reversals for a Balanced String
Given a string containing round, square, and curly brackets, determine whether it is balanced. A string is balanced when every opening bracket is closed by a bracket of the same type in the correct nesting order.
If the string is not balanced, find the minimum number of bracket reversals required to make it balanced. Reversing a bracket changes it to its corresponding bracket of the same type: ( and ), [ and ], or { and }.
Return -1 when the string cannot be made balanced by reversing brackets.
Method Signatures
Check Whether the String Is Balanced
boolean isBalanced(String brackets)
- Returns
true if brackets is already balanced.
- Returns
false otherwise.
Find the Minimum Number of Reversals
int minimumReversals(String brackets)
- Returns
0 if brackets is already balanced.
- Otherwise, returns the minimum number of bracket reversals required to make it balanced.
- Returns
-1 if no sequence of reversals can make the string balanced.
Balanced String Rules
- Every opening bracket must have a corresponding closing bracket.
- Each matched pair must contain brackets of the same type.
- Bracket pairs must be closed in the correct nesting order.
- The empty string is considered balanced.
Constraints
0 ≤ brackets.length() ≤ 200brackets contains only (, ), [, ], {, and }.
Examples
Example 1
isBalanced(brackets = "{[()]}")
Output: true
Every opening bracket is closed by the correct bracket in proper nesting order.
Example 2
minimumReversals(brackets = ")(][")
Output: 4
Reverse all four brackets to obtain ()[].
Example 3
minimumReversals(brackets = "([)]")
Output: -1
Reversing bracket directions cannot correct the crossing order of the round and square bracket types.
Example 4
minimumReversals(brackets = "{{}}[]")
Output: 0
The string is already balanced, so no reversals are required.