title: Find the length of the longest valid parenthesis sequence in a string, in O(n) time
body: <p>My friend ran into a question in an interview and he was told that there is an O(n) solution. However, neither of us can think it up. Here is the question:</p>
  
  <p>There is a string which contains just <code>(</code> and <code>)</code>, find the length of the longest valid parentheses substring, which should be well formed.</p>
  
  <p>For example <code>")()())"</code>, the longest valid parentheses is <code>()()</code> and the length is 4.</p>
  
  <p>I figured it out with dynamic programming, but it is not O(n). Any ideas?</p>
  
  <pre><code>public int getLongestLen(String s) {
      if (s == null || s.length() == 0)
          return 0;
  
      int len = s.length(), maxLen = 0;
      boolean[][] isValid = new boolean[len][len];
      for (int l = 2; l &lt; len; l *= 2)
          for (int start = 0; start &lt;= len - l; start++) {
              if ((s.charAt(start) == '(' &amp;&amp; s.charAt(start + l - 1) == ')') &amp;&amp; 
                  (l == 2 || isValid[start+1][start+l-2])) {
                      isValid[start][start+l-1] = true;
                      maxLen = Math.max(maxLen, l);
                  }
          }
  
      return maxLen;
  }
  </code></pre>