C++ O(n) time and space using Stack and Map


  • 1
    P
    int longestValidParentheses(string s) {
            std::stack<int> st;
            int max = 0;
            std::unordered_map<int, int> prevMap;
            for(int i=0; i < s.size(); i++){
                if(s.at(i) == '('){
                    st.push(i);
                }else{
                    if(st.empty()){
                        continue;
                    }
                    int index = st.top();
                    st.pop();
                    if(prevMap.find(index-1) != prevMap.end()){
                        prevMap[i] = prevMap[index-1]+i-index+1;
                    }else{
                        prevMap[i] = i-index+1;
                    }
                    max = std::max(max, prevMap[i]);
                }
            }
            return max;
        }

Log in to reply
 

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