runtime 0 ms, beats 100% of cpp submissions
O(n) solution with explanation

tags: stack

Longest Valid Parentheses
前置題目

📖 description

給定一個字串，回傳長度最長的括號合法子字串的長度。

ex. 甚麼是合法的字串
    "()"      -> 合法
    "(())()"  -> 合法
    ")()(("   -> 不合法

ex.
    "(()"    : 最長的合法子字串為 "()"
    ")()())" : 最長的合法子字串為 "()()"

🧠 solution

在過去題目中，學會了使用 stack 怎麼判斷一個字串是否合法。
但本題是要找到最長的子字串，先前的判斷過程中，合法的子字串會因為左右 match 而被丟出 stack ，在此可以同樣利用這個想法，因為合法的字串會被丟掉，所以我們只需要紀錄每個符號的位置，然後看到底有多少合法的子字串被丟掉了，並記錄最長的那一個，問題就解決了。

本題雖然難度是 hard ，但其實解法本身非常精簡且簡單，我認為最難的部分是如何想到這個方法，剛看到這類題目其實第一個思路是 sliding window 。

⏳ time complexity

遍歷一次字串，並操作 stack ，每次操作時間複雜度 O(1) ，共 n 次操作
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestValidParentheses(string& s) {
        stack<int> st;
        st.push(-1);    // 確保第一次不會 pop 到空的 stack
        int ma = 0;     // 維護最大值
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                st.push(i); // 遇到左括號就紀錄當前的 index 
            }
            else{
                st.pop();   // 遇到右括號
                if(st.empty()){
                    st.push(i); // 避免 stack 為空 (紀錄下一個合法子字串的開頭)
                }
                else{
                    ma = max(ma,i-st.top());    // 當前合法子字串的開頭
                }
            }
        }
        return ma;
    }
};