Let's make this one less mysterious. For 32. Longest Valid Parentheses, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, two pointers, stack.
The notes already sitting in the source point us in the right direction:
- Brute force
- TLE
- 217 / 230 test cases passed.
- time: O(N^3), space: O(N)
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are isValid, longestValidParentheses, print, stack_contents.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Brute force
02//TLE
03//217 / 230 test cases passed.
04//time: O(N^3), space: O(N)
05class Solution {
06public:
07 bool isValid(string s){
08 stack<char> stk;
09
10 for(char c : s){
11 if(c == '('){
12 stk.push(c);
13 }else{
14 if(!stk.empty() && stk.top() == '('){
15 stk.pop();
16 }else{
17 return false;
18 }
19 }
20 }
21
22 return stk.empty();
23 };
24
25 int longestValidParentheses(string s) {
26 int maxLen = 0;
27
28 for(int i = 0; i < s.size(); ++i){
29 for(int j = 2; i+j-1 < s.size(); ++j){
30 if(isValid(s.substr(i, j))){
31 maxLen = max(maxLen, j);
32 }
33 }
34 }
35
36 return maxLen;
37 }
38};
39
40//DP
41//Runtime: 8 ms, faster than 88.40% of C++ online submissions for Longest Valid Parentheses.
42//Memory Usage: 7.5 MB, less than 22.04% of C++ online submissions for Longest Valid Parentheses.
43//time: O(N), space: O(N)
44class Solution {
45public:
46 int longestValidParentheses(string s) {
47 int n = s.size();
48 //dp[i]: length of longest valid substring ending at i
49 vector<int> dp(n, 0);
50
51 int maxLen = 0;
52
53 //i starts from 1: we can't have a valid substring ending at 0
54 for(int i = 1; i < n; ++i){
55 if(s[i] == ')'){
56 /*
57 dp[i]: length of longest valid substring ending at i
58 s[i] == ')': valid substring can't end at '(', so we don't care it
59 */
60 if(s[i-1] == '('){
61 //"pairs end at i-2" + "()"
62 dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
63 }else{
64 //s[i-1] == ')'
65 if(i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '('){
66 //"pairs end at i-1-dp[i-1]-1"(this could be empty) + '(' + "pairs ends at i-1" + ')'
67 dp[i] = (i-1-dp[i-1]-1 >= 0 ? dp[i-1-dp[i-1]-1] : 0) + 1 + dp[i-1] + 1;
68 }
69 }
70 }
71 maxLen = max(maxLen, dp[i]);
72 }
73
74 return maxLen;
75 }
76};
77
78//stack, not understand
79//Runtime: 8 ms, faster than 88.40% of C++ online submissions for Longest Valid Parentheses.
80//Memory Usage: 7.2 MB, less than 74.62% of C++ online submissions for Longest Valid Parentheses.
81//time: O(N), space: O(N)
82class Solution {
83public:
84 void print(stack<int>& stk){
85 int* end = &stk.top() + 1;
86 int* begin = end - stk.size();
87 vector<int> stack_contents(begin, end);
88
89 //1 4 9 3
90 for(int e : stack_contents){
91 cout << e << " ";
92 }
93 cout << endl;
94 }
95
96 int longestValidParentheses(string s) {
97 int n = s.size();
98 int maxLen = 0;
99 stack<int> stk;
100
101 stk.push(-1);
102
103 for(int i = 0; i < n; ++i){
104 if(s[i] == '('){
105 stk.push(i);
106 }else{
107 stk.pop();
108 if(stk.empty()){
109 //used later, serves as ending of last substring
110 stk.push(i);
111 }else{
112 maxLen = max(maxLen, i - stk.top());
113 }
114 }
115 // print(stk);
116 }
117
118 return maxLen;
119 }
120};
121
122//O(1) space, not understand
123//Proof: https://leetcode.com/problems/longest-valid-parentheses/solution/
124//Runtime: 8 ms, faster than 88.40% of C++ online submissions for Longest Valid Parentheses.
125//Memory Usage: 6.7 MB, less than 98.91% of C++ online submissions for Longest Valid Parentheses.
126//time: O(N), space: O(1)
127class Solution {
128public:
129 int longestValidParentheses(string s) {
130 int n = s.size();
131 int left = 0, right = 0;
132 int maxLen = 0;
133
134 for(int i = 0; i < n; ++i){
135 if(s[i] == '('){
136 ++left;
137 }else{
138 ++right;
139 }
140
141 if(right == left){
142 maxLen = max(maxLen, 2*left);
143 }else if(right > left){
144 //more close than open
145 left = right = 0;
146 }
147 }
148
149 //traverse in reverse order
150 left = right = 0;
151 for(int i = n-1; i >= 0; --i){
152 if(s[i] == '('){
153 ++left;
154 }else{
155 ++right;
156 }
157 if(left == right){
158 maxLen = max(maxLen, 2*left);
159 }else if(left > right){
160 //more close than open
161 left = right = 0;
162 }
163 }
164
165 return maxLen;
166 }
167};Cost
Complexity
Time
O(N), space: O(N)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.