Job for bounties

#1

how to solve this problem

Mike’s boss gave him a string of opening and closing parenthesis asked him to find a valid parenthesis substring in it. He will get number of bounties equal to the length of substring he finds in return. What is the maximum amount of number of bounties he can get?

Input Format
The input file has a single line which contains a single string str that Mike’s boss gave to him.

Constraints
1 <= |str| <= 100000

Output Format
Print, in a single line, the maximum amount of number of bounties Mike can get

Sample Input
(()(()()
Sample Output
4

#2

@bishtmanish786 hey mahvir
A Simple Approach is to find all the substrings of given string. For every string, check if it is a valid string or not. If valid and length is more than maximum length so far, then update maximum length. We can check whether a substring is valid or not in linear time using a stack (See this for details). Time complexity of this solution is O(n2.

An Efficient Solution can solve this problem in O(n) time. The idea is to store indexes of previous starting brackets in a stack. The first element of stack is a special element that provides index before beginning of valid substring (base for next valid string).

  1. Create an empty stack and push -1 to it. The first element
    of stack is used to provide base for next valid string.

  2. Initialize result as 0.

  3. If the character is ‘(’ i.e. str[i] == ‘(’), push index
    ‘i’ to the stack.

  4. Else (if the character is ‘)’)
    a) Pop an item from stack (Most of the time an opening bracket)
    b) If stack is not empty, then find length of current valid
    substring by taking difference between current index and
    top of the stack. If current length is more than result,
    then update the result.
    c) If stack is empty, push current index as base for next
    valid substring.

  5. Return result.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

Your approach is n^3 not n^2. for every sub string n^2 time and checking take n time.