# O(n), easy to understand

• The idea is to decide the boundaries of valid substrings. We scan the string twice, once from the left, and once from the right. Each time we use a stack to keep track the current open brackets ('(' for from-left and ')' for from-right). Once we encounter a close bracket (')' for from-left and '(' for from-right) if the stack is empty, then the current position is a boundary. We mark all the boundaries and then the length of the longest substring without crossing the boundary is the answer.

``````void fromleft(string s, char open, vector<bool>& seg) {
stack<char> st;
for (int i = 0; i < s.length(); i ++) {
if (s[i] == open)
st.push(s[i]);
else {
if (st.empty()) {
int idx = i;
if (open == ')')
idx = s.length()-idx-1;
seg[idx] = true;
}
else st.pop();
}
}
}

class Solution {
public:
int longestValidParentheses(string s) {
vector<bool> seg(s.length());
string sr = s;
reverse(sr.begin(), sr.end());
fromleft(s, '(', seg);
fromleft(sr, ')', seg);

int cur = 0, max_len = 0;
for (int i = 0; i < s.length(); i ++) {
if (seg[i]) {
max_len = max(max_len, cur);
cur = 0;
}
else
cur ++;
}
max_len = max(max_len, cur);
return max_len;
}
};``````

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