Length of the longest valid substring | method to get length of the longest valid ; Create a stack and push - 1 as initial index to it . ; Initialize result ; Traverse all characters of given string ; If opening bracket , push index of it ; If closing bracket ; Pop the previous opening bracket 's index ; Check if this length formed with base of current valid substring is more than max so far ; If stack is empty . push current index as base for next valid substring ( if any ) ; Driver code ; Function call ; Function call
def findMaxLen ( string ) : NEW_LINE INDENT n = len ( string ) NEW_LINE stk = [ ] NEW_LINE stk . append ( - 1 ) NEW_LINE result = 0 NEW_LINE for i in xrange ( n ) : NEW_LINE INDENT if string [ i ] == ' ( ' : NEW_LINE INDENT stk . append ( i ) NEW_LINE DEDENT else : NEW_LINE INDENT if len ( stk ) != 0 : NEW_LINE stk . pop ( ) NEW_LINE if len ( stk ) != 0 : NEW_LINE INDENT result = max ( result , i - stk [ len ( stk ) - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT stk . append ( i ) NEW_LINE DEDENT DEDENT DEDENT return result NEW_LINE DEDENT string = " ( ( ( ) ( ) " NEW_LINE print findMaxLen ( string ) NEW_LINE string = " ( ) ( ( ) ) ) ) ) " NEW_LINE print findMaxLen ( string ) NEW_LINE