Balanced Substrings

CountingStackString

Given a string consisting only of ( and ), you are to determine if it's possible to split the string into exactly two non-empty substrings such that both substrings are balanced. A string is considered balanced if every opening bracket ( has a corresponding closing bracket ) and they are correctly nested.

Example 1

Input

[
  "()()"
]

Output

true

Explanation. The string `()()` can be split into `()` and `()`, both of which are balanced.

Example 2

Input

[
  "(()("
]

Output

false

Explanation. It is not possible to split `(()(` into two non-empty balanced substrings.

Example 3

Input

[
  "(())"
]

Output

true

Explanation. The string `(())` can be split into `(` and `())`, which is not balanced, but it can also be split into `(())` (as a whole) and an empty string, which should be considered invalid as per the problem statement. However, splitting at different positions can yield valid balanced substrings.

Example 4

Input

[
  "()"
]

Output

false

Explanation. The string `()` cannot be split into two non-empty substrings.

Example 5

Input

[
  "()()()"
]

Output

true

Explanation. The string `()()()` has multiple points where it can be split into balanced substrings, such as after the first `()` or the second `()`.

Follow-up: Could you extend your solution to split the string into multiple balanced substrings?

Constraints:

The input string will only contain the characters `(` and `)`. The length of the string will be at least 2 and at most 1000.

Views: 2