Longest Valid Parentheses

Let us have a talk about this problem today. Since in description of this question , definition of "valid(well-formed) " is not very clear, my first submission gave wrong answer. From the test case I failed, I know that cases like "(())" is also considered as valid. After understanding the definition, we can get started.

In my algorithm, firstly, ')'s at beginning of String s are definitely supposed to be ignored, because there is no '(' before them, not possible to form valid parentheses. So we just need to find the first '(' in s. Then I put index of each '(' into a stack(actually implemented by LinkedList), as s is traversed in while loop. If ')' is founded, then it can form a valid parentheses with top element of stack, only when s is not empty( if empty, it means that we have met more ')'s than '(' so far, not possible for this ')' to form valid parentheses), pop out the top, then store indexes of both into a ArrayList in Solution 2(in Solution 1, HashMap, I will talk about the difference later). Now it's time for the key step, merge! We need to merge the new added parentheses with saved ones stored. For case like "()()", when we arrive at index 3, we should know that pair of (0,1) has been stored, and (2,3) is newly added, at this moment, these 2 pairs can be combined together to get a new valid parentheses (0,3). Condition here is that right index of old pair is next to left index of new one. I call this "concatenate". Another special case we need to consider is "(())". If we get to index 3, we can know that (1,2) has been stored, and (0,3) is newly added. We can see that (0,3) just includes (1,2), i.e. 1-0 == 3-2. This is also a condition we should take into account, where merge could happen.

In one iteration, the max time needed for merge is O(i), thus the worst case for finishing this algorithm takes O(n^2) time.

Iterate above process until end of String s is met. Then find the longest valid parentheses stored in the ArrayList. Return the length. (Only takes O(n) time)

Now, what is difference between Solution 1 and 2? HashMap and ArrayList. At first, I chose HashMap, since I store left and right index of parentheses directly, left as key, right as value. However, order of traversal of HashMap is not clear to us. And newly added element is only possible to merge with previously added one. Thus if HashMap is applied, it might take longer time to find the parentheses to merge with the new one. So ArrayList is used. We can start from the end of ArrayList, if the end is not what we need, just break the while loop in merge.

Actually, Solution 1 should return correct result as Solution 2 does. But 1 failed due to TLE!

public class Solution {// case ()((())()
    // Solution 1
    //  public int longestValidParentheses(String s) {
    //     if(s == null || s.length() < 2) return 0;
    //     int longestLen = 0;    
    //     int i = 0;
       
    //     while(i < s.length() && s.charAt(i) == ')'){// find 1st '(' in s
    //         i++;
    //     }
    //     if(i == s.length()) return 0;
    //     LinkedList<Integer> leftList = new LinkedList<Integer>();// store index of left parentheses
    //     HashMap<Integer, Integer> hmLeftRightIdx = new HashMap<Integer, Integer>();// store indexes of //left, right parentheses which are valid
    //     //int leftIdx = -1;
    //     while(i < s.length()){
    //         if(s.charAt(i) == '('){// if '(', we should wait to see what will happen next
    //             leftList.push(i);
    //         }
    //         else{// current char is ')', it is possible to find valid pairs, depending on some conditions
    //             if(!leftList.isEmpty()){// if empty, more ')' exist from index 0 to index i
    //                 int leftIdx = leftList.pop();
    //                 hmLeftRightIdx.put(leftIdx,i);
    //                 merge(hmLeftRightIdx,leftIdx);
    //             }
    //         }
    //         i++;
    //     }
    //     if(hmLeftRightIdx.isEmpty()) return 0;
       
    //     for(Integer index:hmLeftRightIdx.keySet()){
    //         int len = hmLeftRightIdx.get(index) - index + 1;
    //         if(len>longestLen) longestLen = len;  
    //     }
       
    //     return longestLen;
    // }
    // public void merge(HashMap<Integer, Integer> hmLeftRightIdx, int leftIdx){
    // if (hmLeftRightIdx.size() < 2 || !hmLeftRightIdx.containsKey(leftIdx)) return;
    //                 int rightIdx = hmLeftRightIdx.get(leftIdx);
    //                 boolean addedFlag = false;
    //                 int idxMerge= -1;
    //                 for(Integer index:hmLeftRightIdx.keySet()){
    //                 if(index != leftIdx){
    //                 if((leftIdx - hmLeftRightIdx.get(index)) == 1
    //                 ||((index - leftIdx) == (rightIdx - hmLeftRightIdx.get(index)) )){//2 '(' close to //each other, merge them, store smaller index and new length
    //                 addedFlag = true;
    //                 idxMerge = index;
    //                 break;
    //                 }
    //                 }
    //                 }
    //                 if(addedFlag && (leftIdx - hmLeftRightIdx.get(idxMerge)) == 1){// concatenate
    //                     int newRight = hmLeftRightIdx.get(leftIdx);
    //                     hmLeftRightIdx.remove(leftIdx);
    //                     hmLeftRightIdx.put(idxMerge,newRight);
    //                     merge(hmLeftRightIdx,idxMerge);
    //                 }
                   
    //                 else{// include or cover
    //                     if(addedFlag){
    //                         hmLeftRightIdx.remove(idxMerge);
    //                         merge(hmLeftRightIdx,leftIdx);
    //                     }
    //                 }                  
    // }

    // Solution 2:
    public int longestValidParentheses(String s) {
        if(s == null || s.length() < 2) return 0;
        int longestLen = 0;    
        int i = 0;
       
        while(i < s.length() && s.charAt(i) == ')'){// find 1st '(' in s
            i++;
        }
        if(i == s.length()) return 0;
        LinkedList<Integer> leftList = new LinkedList<Integer>();
        ArrayList<DT> arrLeftRightIdx = new ArrayList<DT>();
        while(i<s.length()){
            if(s.charAt(i) == '('){// if '(', we should wait to see what will happen next
                leftList.push(i);
            }
            else{// current char is ')', it is possible to find valid pairs, depending on some conditions
                if(!leftList.isEmpty()){// if empty, more ')' exist from index 0 to index i
                    int leftIdx = leftList.pop();
                    DT dt = new DT(leftIdx,i);
                    arrLeftRightIdx.add(dt);
                    merge(arrLeftRightIdx);
                }
            }
            i++;          
        }
       
      for(DT dt:arrLeftRightIdx){
      int len = dt.right - dt.left + 1;
      if(len>longestLen) longestLen = len;  
  }
       
        return longestLen;
    }
   
    public void merge(ArrayList<DT> arrLeftRightIdx){
        if(arrLeftRightIdx.size()<2) return;
        int i = arrLeftRightIdx.size() - 1;
       
        while( i >= 1 &&( ((arrLeftRightIdx.get(i).left - arrLeftRightIdx.get(i-1).right) == 1) ||((arrLeftRightIdx.get(i-1).left - arrLeftRightIdx.get(i).left)==(arrLeftRightIdx.get(i).right-arrLeftRightIdx.get(i-1).right)))){
            if((arrLeftRightIdx.get(i).left - arrLeftRightIdx.get(i-1).right) == 1){// concatenate
                int newRight = arrLeftRightIdx.get(i).right;
                int newLeft = arrLeftRightIdx.get(i-1).left;
                arrLeftRightIdx.remove(i);
                arrLeftRightIdx.remove(i-1);
                DT dt = new DT(newLeft,newRight);
                arrLeftRightIdx.add(dt);
            }
            else{// include
                arrLeftRightIdx.remove(i-1);
            }
            i--;
        }
    }
}

class DT{
    public int left;
    public int right;
    DT(int x, int y){left = x; right = y;}
}