Balanced Parentheses Subsequence
MediumPractice library · +20 XPqueuestacksimulation
Given a string consisting of '(' and ')', find the length of the longest subsequence that forms a balanced parentheses string. A balanced parentheses string is defined as follows:
- The empty string is balanced.
- If S is a balanced string, then (S) is balanced.
- If S and T are balanced strings, then ST is balanced.
For example, "()()", "(())()", "" are balanced, while ")(", "(()" are not.
Print the length of the longest balanced parentheses subsequence.
Input
A single line containing a string S (1 <= |S| <= 200000) consisting only of '(' and ')' characters.
Output
A single integer: the length of the longest balanced parentheses subsequence.
Constraints
1 <= |S| <= 200000
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
(()))((()))
Output
10
The longest balanced subsequence is '(())(())', length 10.
Example 2
Input
)()(
Output
2
The longest balanced subsequence is '()', length 2.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
(()))((()))
Example 2 input
)()(