[InterviewBit] Longest valid Parentheses

Longest valid Parentheses

  • Time :
  • Space :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Solution::longestValidParentheses(string A) {
int res = 0;
vector<int> st;
for(int i = 0; i < A.length(); i++) {
if(A[i] == '(') st.push_back(i);
else {
if(!st.empty() and A[st.back()] == '(') {
st.pop_back();
res = max(res, i - (st.empty() ? -1 : st.back()));
} else st.push_back(i);
}
}
return res;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/09/14/PS/interviewbit/longest-valid-parentheses/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.