TLE on the last test case. Passes when run individually! Any suggestions?


  • 0
    K

    Used character index to calculate the longest valid ones.

    1. Used two stack. stack1 stores the invalid indexes, stack2 stores the valid indexes.
    2. For any two consecutive invalid indexes in stack1, add all the valid indexes that fall in that range in stack2.
      Eg: stack1 = [2,6,8], stack2 = [0,1,3,4,5,7]. [3,4,5] is the longest valid index and therefore the length is 6.
    3. Compute the max on every iteration.
    public class Solution {
        
        class CharacterIndex {
    		char c;
    		int index;
    		
    		public CharacterIndex(char c, int index) {
    			this.c = c;
    			this.index = index;
    		}
        }
        	
        public int longestValidParentheses(String s) {
    		char[] c = s.toCharArray();
    		int max = 0;
    		int curr = max;
                    // valid indexes
    		Stack<CharacterIndex> stack1 = new Stack<>();
                    // invalid indexes
    		Stack<CharacterIndex> stack2 = new Stack<>();
                    // Push valid and invalid indexes to stack2 and stack1 respectively.
    		for(int i=0;i<c.length;i++) {
    			if(c[i] == '(' || (c[i] == ')' && stack1.isEmpty()) 
    			               || (c[i] == ')' && stack1.peek().c == ')')) 
    			{
    				stack1.push(new CharacterIndex(c[i], i));
    			} else {
    				if(!stack1.isEmpty()) stack2.push(stack1.pop());
    			}
    		}
                    // Base case. No valid indexes.
    		if(stack2.isEmpty()) return max;
                    // Compute the longest valid ones.
    		while(!stack1.isEmpty() || !stack2.isEmpty()) {			
    			while(!stack1.isEmpty()) {
    				while(!stack2.isEmpty() && (stack2.peek().index > stack1.peek().index)) {
    					stack2.pop();
    					curr += 2;
    				}
    				stack1.pop();
    				max = Math.max(max, curr);
    				curr = 0;
    			}
    			if(stack1.isEmpty()) {
    				while(!stack2.isEmpty()) {
    					curr += 2;
    					stack2.pop();
    				}
    				return Math.max(max, curr);
    			}
    		}		
    		return Math.max(max, curr);
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.