the art of
Algorithm
Notes on Analysis and Design



Longest Balanced Subsequence

The following function helps in determining the length of longest balanced subsequence in the string S

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longest(s):
    match = [0] * (len(s) + 1)
    for i in xrange(1, len(s)):
        if s[i] in '({[':
            continue
        open = '({['[')}]'.index(s[i])]
        start = i - 1 - match[i - 1]
        if start < 0: continue
        if s[start] != open: continue
        match[i] = i - start + 1 + match[start - 1]
    best = max(match)
    end = match.index(best)
    return len(s[end + 1 - best:end + 1])
s=raw_input()
print longest(s)