Question

Ram was going through the concept of parenthesis. He got stuck in some question.Your task is to help him in solving the question. He has to tell the maximum length atwhich parenthesis are balanced. Its now your task to display the maximum number.5Input Description: You are given a string 's of parentesis.Output Description : Print the maximum length of balanced parenthesis else if it no balancedparenthesis length exists print -1.9Samole Input: ")(0)Sample Outout : 4.​

Answer 1

Answer :

The idea is take value of open bracket ‘(‘ as 1 and value of close bracket ‘)’ as -1. Now start finding the prefix sum of the given string. The farthest index, say maxi, where the value of sum is 0 is the index upto which longest balanced prefix exists. So the answer would be maxi + 1.

Below is the implementation of this approach:

Answer 2

Answer:

def maxbalancedprefix (str, n):

   _sum = 0

   maxi = 0

   for i in range(n):

       if str[i] == '(':

           _sum += 1

       else:

           _sum -= 1

       if _sum < 0:

           break

       if _sum == 0:

           maxi = i + 1

   return maxi

str = '((()())())(('

n = len(str)

print(maxbalancedprefix (str, n))

Explanation:

• The aim is to treat the values of the open brackets () and (), respectively, as 1 and -1.
• Now begin calculating the supplied string's prefix sum.
• The furthest index, let's say maxi, when sum has a value of 0, is the index up to which the longest balanced prefix is present.
• The solution would therefore be maxi plus 1.def maxbalancedprefix (str, n):

#SPJ2