Balanced Subsequences
Anya loves the simple beauty of balanced sequences. She has a sequence of opening and closing brackets, represented by the characters '(' and ')'. A subsequence of this sequence is formed by deleting zero or more characters from the original sequence. Anya wants to find the length of the longest possible subsequence that is also a balanced bracket sequence. A bracket sequence is balanced if:
- It is empty.
- It can be written as AB, where A and B are balanced bracket sequences.
- It can be written as (A), where A is a balanced bracket sequence.
For example, "()()" and "(())()" are balanced, but ")(" and "(()" are not.
Help Anya find the length of the longest balanced subsequence she can form from her given bracket sequence.
Input
The first line contains a single integer N, the length of the bracket sequence. The second line contains a string of N characters, consisting only of '(' and ')'.
Output
A single integer: the length of the longest balanced subsequence.
Constraints
1 <= N <= 200000 The string contains only '(' and ')' characters.
Example 1
6 (()())
6
The entire string is a balanced subsequence.
Example 2
7 ())((()))
8
The longest balanced subsequence is "()(())" with length 6. The first ')' is unmatched.
Hints
Similar problems
- Maximum Sum of Non-Overlapping Positive SubarraysMedium
- Distinct Elements CountMedium
- Distinct Elements in Sliding WindowMedium
- Longest Prefix with Equal CountsMedium
- Distinct Element Sum with Minimum CostMedium
- Distinct Elements with Minimum Total CostMedium
More topics: Hash Map and Hashing problems, Greedy problems, Stack problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
6 (()())
7 ())((()))