I want to take a second to explore the Length of Balanced Subsequence problem from binarysearch.io
The Problem
So, if s is “())(()”, then the return would be 4 since the longest subsequence is “()()”, a rebalancing of “))((“. This means that the pairs don’t have to be contiguous.
The Solution
Since the pairs don’t need to be contiguous, then our main goal is to keep track of each opened parenthesis. We can accomplish this with a for loop, but we will also need a counter to incremate with each non-closed open parenthesis. If we hit a closed parenthesis any time after we hit an open one that still needs to be closed, we can add 2 to our counter since a full “()” pair is completed. After we just complete a pair, we will decrement our counter, so that the number of open parentheses is tracked properly. Our conditionals will track and only trigger if our counter is greater than zero, so we don’t great imbalanced pairs. My solution ended up looking like this:
I hope this helped clarify a potentially complicated yet simple prompt.
