Find the length of the longest balanced subsequence in Python

In this article, we are going to find the length of the longest balanced subsequence in Python. Subsequence means it can be part of the sequence but need not be contiguous. Let’s see some inputs and outputs to better understand the problem.

Input:    (())()())
Output: 8 #since longest balanced subsequence is: (())()()
Input: ()(()(()
Output: 6 #since longest balanced subsequence is: ()()()
Input: ((((
Output: 0 #since longest balanced subsequence is:

Plan of Attack

The main idea to solve this problem is to use the stack. but here we aren’t checking the balanced or not. hence it won’t be viable. So what we are going to do is we will iterate over string from start to end. we will count the number of not balanced starting ‘(‘ and ending ‘)’. In this process, we will maintain a variable to add and subtract in respective cases. Let’s see the cases.

we will have a variable called badones, when we encountered a start parenthesis we will add one. When we encountered a  closing parenthesis, There are two possibilities, one we encountered a closed for opened one { like () } another is one which doesn’t have a starting parenthesis.

When the variable badones is zero, which means that there is no start parenthesis which is waiting for it’s closed parenthesis to encounter hence in this case add one. If the badones variable value is other than zero we will subtract one from the variable. After iterating the complete sequence, the value in the variable badones says that how many are there without closing. if we subtract this number from the length of the sequence. We get the length of longest subsequence. Let’s see the Python code:

seq = input()
badones = 0
for i in range(len(seq)):
  if seq[i]=='(':
    #we add one since we don't whether it has respective ')' or not
    badones+=1
  else:
    if badones==0:
      #badones zero mean no '(' but we encountered ')'
      badones+=1
    else:
      #badones not zeros means the encountered ')' has respective '('
      badones-=1
  #we subtract no.of.badones from length of sequence to get answer
print(f"lenght of longest balanced sequence in {seq}: {len(seq)-badones}")

We iterated through the whole sequence once so the time-complexity is big-O(n)
We have used only variable mainly hence space-complexity is big-O(1)

Please feel free to comment down your doubts and thoughts.

Leave a Reply

Your email address will not be published. Required fields are marked *