aboutsummaryrefslogtreecommitdiff
path: root/other/longest_valid_parentheses.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/longest_valid_parentheses.cpp')
-rw-r--r--other/longest_valid_parentheses.cpp41
1 files changed, 41 insertions, 0 deletions
diff --git a/other/longest_valid_parentheses.cpp b/other/longest_valid_parentheses.cpp
new file mode 100644
index 0000000..953e8be
--- /dev/null
+++ b/other/longest_valid_parentheses.cpp
@@ -0,0 +1,41 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int longestValidParentheses(string s) {
+ int n = s.size(), ans = 0;
+ stack<int> stk;
+ for (int i = 0; i < n; i++) {
+ if (s[i] == '(')
+ stk.push(i);
+ else {
+ if (!stk.empty()) {
+ if (s[stk.top()] == '(')
+ stk.pop();
+ else
+ stk.push(i);
+ } else
+ stk.push(i);
+ }
+ }
+ if (stk.empty())
+ ans = n;
+ else {
+ int a = n, b = 0;
+ while (!stk.empty()) {
+ b = stk.top();
+ stk.pop();
+ ans = max(ans, a - b - 1);
+ a = b;
+ }
+ ans = max(ans, a);
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ string s = ")()())";
+ cout << obj.longestValidParentheses(s);
+}