Why people give conclusion that this cannot be done with O(1) space? my AC solution: O(n) run time, O(1) space


  • 8
    B
    public class Solution {
        public int longestValidParentheses(String s) {
          return ltr(s, 0, s.length());
        }
    
        public int ltr(String s, int start, int end) {
          int left = start;
          int openLeft = 0;
          int max = 0;
          for(int i = start; i < end; i++) {
            if(s.charAt(i) == '(')
              openLeft++;
            else
              openLeft--;
            if(openLeft < 0) {
              int length = i - left;
              if(length > max)
                max = length;
              left = i + 1;
              openLeft = 0;
            }
          }
          if(openLeft == 0) {
            int length = end - left;
            if(length > max)
              max = length;
          } {
            int length = rtl(s, left, end);
            if(length > max)
              max = length;
          }
          return max;
        }
    
        public int rtl(String s, int start, int end) {
          int right = end;
          int openRight = 0;
          int max = 0;
          for(int i = end - 1; i >= start; i--) {
            if(s.charAt(i) == ')')
              openRight++;
            else
              openRight--;
            if(openRight < 0) {
              int length = right - (i + 1);
              if(length > max)
                max = length;
              right = i;
              openRight = 0;
            }
          }
          if(openRight == 0) {
            int length = right - start;
            if(length > max)
              max = length;
          }
          return max;
        }
      }
    

    I am pretty sure the code can be shorten to maybe half of the current size...... but why bother...
    The idea is very simple, 2 iteration at most. First time from left to right, second time from right to left.

    The second iteration is only needed if the first iteration has ends with unclosed left bracket.


  • 1
    B

    I will explain if anyone find the logic confusing.


  • 0
    M

    Can u explain it? It is really confusing.


  • 0
    B

    so when the first iteration ends (left to right), we have 2 scenarios: 1, all left brackets are closed (every left bracket matches a right bracket) 2, some left brackets are open (couldn't find enough right brackets to finish them). In the first case, things are perfect, we just return the max value. In the second case, we start the second iteration from right to left. This time, we try to find left brackets to match right brackets. Remember, the condition to start the second iteration is that we are having more left brackets than right brackets. Therefore, we know each right bracket will guarantee to find a left bracket to form a pair.


  • 0
    S

    I'll give you that for O(1) space.


  • 2
    Q
    // LeetCode, Longest Valid Parenthese
    // 两遍扫描,时间复杂度O(n),空间复杂度O(1)
    // @author 曹鹏(http://weibo.com/cpcs)
    class Solution {
    public:
        int longestValidParentheses(string s) {
            int answer = 0, depth = 0, start = -1;
            for (int i = 0; i < s.size(); ++i) {
                if (s[i] == '(') {
                    ++depth;
                } else {
                    --depth;
                    if (depth < 0) {
                        start = i;
                        depth = 0;
                    } else if (depth == 0) {
                        answer = max(answer, i - start);
                    }
                } 
            }
    
            depth = 0;
            start = s.size();
            for (int i = s.size() - 1; i >= 0; --i) {
                if (s[i] == ')') {
                    ++depth;
                } else {
                    --depth;
                    if (depth < 0) {
                        start = i;
                        depth = 0;
                    } else if (depth == 0) {
                        answer = max(answer, start - i);
                    }
                } 
            }
            return answer;
        }
    };

  • 0
    Z

    try this test case '()(()))(' , i think the answer should be 2 ,but the program gives me a 6


  • 0
    S

    ()(()) is 6, consecutive parentheses is treated as valid parentheses


  • 0
    B

    Thank you for explaining this to zhiyuan.MA.chn. I think 6 is the right answer for the given input.


  • 0
    W

    hi I am agree with you! I used two scan for the input : one from left to right and another from right to left. the time complexity is O(n) and space complexity is O(1)


  • 0
    R

    Oh, the post code(@beijunyi) is not similar with @Qili1 , Not SAME logic !!! please pay attention !

    the first's backward's interval is [postForwardLastStartPos, end] , while the second use [0, end] !

    They are all right , but you can't mess the interval ! because I got errors for mess it. ...


Log in to reply
 

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