O(n) in time O(1) in space?


  • 4
    T

    Could there be better improvements on this?

    public class Solution {
        public int longestValidParentheses(String s) {
        	int length = 0;
            int score = 0;
            int start = 0;
            int cur = 0;
            int bound;
            
            while (cur < s.length()) {
                score += (s.charAt(cur) == '(') ? 1 : -1;
                
                if (score == 0) {
                    length = Math.max(length, cur - start + 1);            	
                } else if (score < 0) {
                    start = cur + 1;
                    score = 0;
                }
    
                ++cur;
            }
            
            if (score > 0) {
                bound = start - 1;
                cur = s.length() - 1;
                start = cur;
                score = 0;
                
                while (cur > bound) {
                    score += (s.charAt(cur) == ')') ? 1 : -1;
                    
                    if (score == 0) {
                        length = Math.max(length, start - cur + 1);            	
                    } else if (score < 0) {
                        start = cur - 1;
                        score = 0;
                    }
                    
                    --cur;
                }
            }
            
            return length;
        }
    }

  • 0
    S

    O(1) space is really hard.


  • 1
    Q

    Excellent answer with 9ms test time, but can you explain a little more?


  • 0
    T

    I view this question in this way:

    First of all, it is clear that a valid parentheses sequence should always have equal number of '(' and ')'. But it is not enough to judge it without the consideration of parentheses ordering.

    So in this solution, it firstly inspect a parentheses sequence from left to right to guarantee that the ')' will never outnumber '(', that is, 'score' variable should never be less than 0. Because if ')' outnumbers '(' in a sequence when looking from left to right, it implies that this sub-sequence is invalid. So, whenever this invalid sub-sequence is detected, we just reset our start index of the candidate sub-sequence and move on. And for the case that 'score' variable equals 0, it means that a valid sub-sequence is detected. So we update our length in that case.

    However, just looking a sequence from left to right can only find the longest valid parentheses when the 'score' variable of a checked sequence ends with non-positive numbers. There is an additional case to be considered: what if '(' outnumbers ')' at the end of the sequence? If '(' outnumbers ')', we may never know the length of the valid parentheses in that sub-sequence

    In that case, we need to check the sequence again from right to left. The mechanism works similar to the first round of checking above.

    By performing this inspection forwardly and backwardly, the longest valid parentheses would be found.


  • 0
    W

    Thanks! Best solution and explanation I've ever seen!


Log in to reply
 

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