Count Valid Parentheses Strings

Dynamic ProgrammingStackString

Given a string containing only the characters ( and ), count how many segments of the string form a valid parentheses combination. A valid parentheses combination means that each opening parenthesis ( has a corresponding closing parenthesis ) and they are in the correct order.

Example 1

Input

[
  "()"
]

Output

Explanation. There is 1 valid segment `()`, which is a valid parentheses combination.

Example 2

Input

[
  "())"
]

Output

Explanation. The segment `()` is valid but `)` is not paired, so there is only 1 valid segment.

Example 3

Input

[
  "(())"
]

Output

Explanation. The segment `(())` is valid as both pairs of parentheses close correctly.

Example 4

Input

[
  "()()"
]

Output

Explanation. There are two valid segments `()` and `()`.

Example 5

Input

[
  "((()))"
]

Output

Explanation. The segment `((()))` includes nested valid pairs, forming one complete valid segment.

Example 6

Input

[
  "((())())"
]

Output

Explanation. The segments `(())` and `()` both form valid parentheses combinations, totaling two.

Follow-up: How would you modify your solution if the string could include other characters such as `{}` and `[]` and you need to validate combinations of all these types?

Constraints:

The input string will only contain the characters `(` and `)`. The string will not exceed 100 characters in length.

Views: 2