Find Longest valid Parentheses Length [ Google ]


Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis sub string.[Courtesy: geeksforgeeks]

Problem Link

Solution: The problem can be solved with DP approach . And also as counting the left and right parenthesis from left to right.If the left parenthesis count is less than the right parenthesis count , then it means that validity of the parsed string  is invalid from this point. Find the longest valid length when left and right counts are equal . Start counting again left and right parenthesis count from 0 when left becomes less than right count.

Do the above approach from right to left of the string again.

DP approach:


Comments are closed.