Teaching Kids Programming – Length of Longest Balanced Subsequence

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s containing brackets “(” and “)”, return the length of the longest subsequence of balanced brackets.

Constraints
n ≤ 100,000 where n is length of s.
Example 1
Input
s = “())(()”
Output
4
Explanation
We can take the subsequence “()()”

Example 2
Input
s = “))((”
Output
0
Explanation
We can’t take any letters from s that’s balanced, so the longest balanced subsequence is “” (empty string).

Example 3
Input
s = “))()))()”
Output
4
Explanation
We can take the subsequence “()()”. Note that characters in the subsequence do not have to be contiguous.

Example 4
Input
s = “((((())”
Output
4
Explanation
We can make the subsequence (()).

Length of Longest Balanced Subsequence

We use a counter (balance) that is incremented when we meet opening bracket and decremented when we meed closing bracket. However, the balance never falls below zero, and when it is non-negative after we meet ‘)’ we know we have a corresponding ‘(‘ and therefore we can construct one more pair of balanced brackets.

class Solution:
    def longestBalanceSubsequence(self, s):
        ans = bal = 0
        for i in s:
            if i == '(':
                bal += 1
            else:
                bal -= 1
                if bal >= 0:
                    ans += 1
                else:
                    bal = 0
        return ans << 1

Time complexity is O(N) where N is the number of the brackets in the string. Space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —