Range Queries for Longest Correct Bracket Subsequence Set | 2 | Function for precomputation ; Create a stack and push - 1 as initial index to it . ; Traverse all characters of given String ; If opening bracket , push index of it ; If closing bracket , i . e . , str [ i ] = ')  ; If closing bracket , i . e . , str [ i ] = ' ) ' && stack is not empty then mark both " open ▁ & ▁ close " bracket indexs as 1 . Pop the previous opening bracket 's index ; If stack is empty . ; Function return output of each query in O ( 1 ) ; Driver code
def constructBlanceArray ( BOP , BCP , str , n ) : NEW_LINE INDENT stk = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( str [ i ] == ' ( ' ) : NEW_LINE INDENT stk . append ( i ) ; NEW_LINE DEDENT else : NEW_LINE INDENT if ( len ( stk ) != 0 ) : NEW_LINE INDENT BCP [ i ] = 1 ; NEW_LINE BOP [ stk [ - 1 ] ] = 1 ; NEW_LINE stk . pop ( ) ; NEW_LINE DEDENT else : NEW_LINE INDENT BCP [ i ] = 0 ; NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT BCP [ i ] += BCP [ i - 1 ] ; NEW_LINE BOP [ i ] += BOP [ i - 1 ] ; NEW_LINE DEDENT DEDENT def query ( BOP , BCP , s , e ) : NEW_LINE INDENT if ( BOP [ s - 1 ] == BOP [ s ] ) : NEW_LINE INDENT return ( BCP [ e ] - BOP [ s ] ) * 2 ; NEW_LINE DEDENT else : NEW_LINE INDENT return ( BCP [ e ] - BOP [ s ] + 1 ) * 2 ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT string = " ( ) ) ( ( ) ) ( ( ) ) ( " ; NEW_LINE n = len ( string ) NEW_LINE BCP = [ 0 for i in range ( n + 1 ) ] ; NEW_LINE BOP = [ 0 for i in range ( n + 1 ) ] ; NEW_LINE constructBlanceArray ( BOP , BCP , string , n ) ; NEW_LINE startIndex = 5 NEW_LINE endIndex = 11 ; NEW_LINE print ( " Maximum ▁ Length ▁ Correct ▁ " + " Bracket ▁ Subsequence ▁ between ▁ " + str ( startIndex ) + " ▁ and ▁ " + str ( endIndex ) + " ▁ = ▁ " + str ( query ( BOP , BCP , startIndex , endIndex ) ) ) ; NEW_LINE startIndex = 4 ; NEW_LINE endIndex = 5 ; NEW_LINE print ( " Maximum ▁ Length ▁ Correct ▁ " + " Bracket ▁ Subsequence ▁ between ▁ " + str ( startIndex ) + " ▁ and ▁ " + str ( endIndex ) + " ▁ = ▁ " + str ( query ( BOP , BCP , startIndex , endIndex ) ) ) NEW_LINE startIndex = 1 ; NEW_LINE endIndex = 5 ; NEW_LINE print ( " Maximum ▁ Length ▁ Correct ▁ " + " Bracket ▁ Subsequence ▁ between ▁ " + str ( startIndex ) + " ▁ and ▁ " + str ( endIndex ) + " ▁ = ▁ " + str ( query ( BOP , BCP , startIndex , endIndex ) ) ) ; NEW_LINE DEDENT