daihan's blog

Longest Balanced parantheses HELP PLEASE
By daihan, 8 years ago, In English

UPD : Bug found . :)

I got a problem in here : Link . In this problem they said :

Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis substring.

Examples:

Input : ((()

Output : 2

Explanation : ()

Input: )()())

Output : 4

Explanation: ()()

Input: ()(()))))

Output: 6

Explanation: ()(())

My code : link here

Getting WA.

My logic is : If i got a balanced parentheses then i store the first and last index of this into vector vct . Then after storing in this manner . I check if(vct[i].first==vct[i-1].second+1) that means ith BP(balanced parentheses) and (i-1)th BP are neighour to each other , then i merge those two BP's length , if that condition is not true then , update sum=vct[i].second-vct[i].first+1 // length of ith BP . I update maximum length by this mx=max(mx,sum) ; . But getting Wrong answer . Can anyone guess the bug . Please help .

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Lets keep stack of positions and pos, where pos — current start position. If in some moment we meet open bracket than we should add this position in stack, otherwise if stack is empty than just move pos to i, in other case pop last position from stack and try ans = max(ans, i - stack.top()) or ans = max(ans, i - pos) if it's empty .

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

((()()()(())). your code is giving 12 as answer but answer should be 10.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

take this case . (((())))(()()). answer should be 14 , but your code is returning 8.

→ Reply