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) |