package kata;

import java.util.*;

/**
 * https://leetcode.com/problems/longest-valid-parentheses
 */
public class LongestValidParentheses {
  static int longestValidParentheses(String str) {
    Stack<Integer> invalids = new Stack<>();
    invalids.push(-1);

    int max = 0;
    for (int i = 0; i < str.length(); i++) {
      if (str.charAt(i) == '(') {
        invalids.push(i);
      } else {
        invalids.pop();
        if (invalids.isEmpty()) {
          // The string is invalid up to i
          invalids.push(i);
        } else {
          max = Math.max(max, i - invalids.peek());
        }
      }
    }
    return max;
  }

  public static void main(String args[]) {
    runSample("(()"); // 2
    runSample(")()())"); // 4
    runSample("(()())"); // 6
    runSample("())"); // 2
  }

  static void runSample(String s) {
    System.out.printf("%s = %s\n", s, longestValidParentheses(s));
  }
}

@@ -635,16 +635,514 @@
 x;%0A  %7D%0A%0A
+  // This does not work for )()()) -%3E 2 (correct answer is 4)%0A  // We need to keep track of the invalids, not valid.%0A  static int longestValidParentheses2(String str) %7B%0A    Stack%3CInteger%3E openIndices = new Stack%3C%3E();%0A%0A    int max = 0;%0A    for (int i = 0; i %3C str.length(); i++) %7B%0A      if (str.charAt(i) == '(') %7B%0A        openIndices.push(i);%0A      %7D else %7B%0A        if (!openIndices.isEmpty()) %7B%0A          max = Math.max(max, i - openIndices.pop() + 1);%0A        %7D%0A      %7D%0A    %7D%0A    return max;%0A  %7D%0A
   public

add an explanation why an alternative does not work