title: Length of longest chain of balanced parentheses in given ranges
body: <blockquote>
    <p>First, define a string of "balanced" parentheses as a string such that
    for every '(' there is one unique, matching ')' somewhere after that
    '('.</p>
    
    <p>For example, the following strings are all "balanced":</p>
    
    <p>()</p>
    
    <p>()()</p>
    
    <p>(())()</p>
    
    <p>while these are not:</p>
    
    <p>)( </p>
    
    <p>())(</p>
    
    <p>Given a string of parentheses (length &lt;= 1,000,000) and a list of range queries, find the
    maximum length of balanced parentheses within each of the ranges for
    each of the &lt;= 100,000 queries (using 0-indexing for the ranges)</p>
    
    <p>Ex:</p>
    
    <p>()))()(())</p>
    
    <p>Range: [0,3] -> Longest = 2 : "()"</p>
    
    <p>Range: [0, 4] -> Longest  = 2 : "()"</p>
    
    <p>Range: [5, 9] -> Longest = 4: "(())"</p>
  </blockquote>
  
  <p>My thoughts are as follows:</p>
  
  <p>First, just determining whether a string is "balanced" can be done by maintaining a stack. If you encounter a '(', push into the stack and when you encounter a ')', pop out of the stack. If at the end any '(' remains, then the string is not "balanced." </p>
  
  <p>However, repeating this for all the ranges is O(N*M) complexity which is too long for the size of the inputs.</p>
  
  <p>Now, upon noticing the range queries, prefix sums and binary indexed trees/segment trees come to mind. If you can precompute the entire prefix sum range into an array, then you can find smaller prefix sums by taking the difference, which will have good big-o complexity.</p>
  
  <p>I had the idea of assigning a +1 value to a '(' and a -1 value to a ')' so that way every time you encounter a '(' you add one to the cumulative sum and when you encounter a ')' you decrease. So for a valid, "balanced" string like <code>))()</code> you would get: <code>-1 -2 -1 -2</code>.</p>
  
  <p>However, my question is how do you use this to determine if it is "balanced"? Also, because you need to find the largest "balanced" string within a given interval, how do you use the ability to check if a given substring is "balanced" to find this largest within that given interval.</p>