Let's make this one less mysterious. For 5. Longest Palindromic Substring, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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.
The notes already sitting in the source point us in the right direction:
- Approach 3: Dynamic Programming
- https://ithelp.ithome.com.tw/articles/10215365
- time: O(N^2), space: O(N^2)
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are longestPalindrome, rs, expandAroundCenter, t, p.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- 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^2), space: O(N^2)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Approach 3: Dynamic Programming
02//https://ithelp.ithome.com.tw/articles/10215365
03//Runtime: 924 ms, faster than 6.44% of C++ online submissions for Longest Palindromic Substring.
04//Memory Usage: 24.3 MB, less than 21.38% of C++ online submissions for Longest Palindromic Substring.
05//time: O(N^2), space: O(N^2)
06class Solution {
07public:
08 string longestPalindrome(string s) {
09 int n = s.size();
10 vector<vector<bool>> dp(n, vector(n, false));
11 string ans;
12
13 for(int i = n-1; i >= 0; i--){
14 for(int j = i; j < n; j++){
15 //susbstring: s[i...j]
16 //length 1
17 if(i == j){
18 dp[i][j] = true;
19 }else if(i+1 == j){
20 dp[i][j] = (s[i] == s[j]);
21 }else{
22 dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
23 }
24
25 if(dp[i][j] && j-i+1 > ans.size()){
26 ans = s.substr(i, j-i+1);
27 }
28 }
29 }
30
31 return ans;
32 }
33};
34
35//same as above, space complexity O(n)
36//Runtime: 904 ms, faster than 7.04% of C++ online submissions for Longest Palindromic Substring.
37//Memory Usage: 14.6 MB, less than 40.00% of C++ online submissions for Longest Palindromic Substring.
38class Solution {
39public:
40 string longestPalindrome(string s) {
41 int n = s.size();
42 vector<vector<bool>> dp(2, vector(n, false));
43 string ans;
44
45 for(int i = n-1; i >= 0; i--){
46 for(int j = i; j < n; j++){
47 //susbstring: s[i...j]
48 //length 1
49 if(i == j){
50 dp[i%2][j] = true;
51 }else if(i+1 == j){
52 dp[i%2][j] = (s[i] == s[j]);
53 }else{
54 dp[i%2][j] = (s[i] == s[j]) && dp[(i+1)%2][j-1];
55 }
56
57 if(dp[i%2][j] && j-i+1 > ans.size()){
58 ans = s.substr(i, j-i+1);
59 }
60 }
61 }
62
63 return ans;
64 }
65};
66
67//Approach 1: Longest Common Substring
68//https://www.geeksforgeeks.org/longest-common-substring-dp-29/
69//Runtime: 664 ms, faster than 10.25% of C++ online submissions for Longest Palindromic Substring.
70//Memory Usage: 191.6 MB, less than 5.51% of C++ online submissions for Longest Palindromic Substring.
71//time: O(N^2), space: O(N^2)
72class Solution {
73public:
74 string longestPalindrome(string s) {
75 int n = s.size();
76 string rs(s.rbegin(), s.rend());
77 string ans = "";
78
79 //find s and rs's longest common substring
80
81 vector<vector<int>> dp(n+1, vector(n+1, 0));
82
83 for(int i = 1; i <= n; i++){
84 for(int j = 1; j <= n; j++){
85 if(s[i-1] == rs[j-1]){
86 dp[i][j] = dp[i-1][j-1] + 1;
87 }else{
88 dp[i][j] = 0;
89 }
90
91 /*
92 the additional condition turns the problem from
93 longest common substring to longest palindrome,
94 because it restricts the position of lc substring
95 */
96 if(dp[i][j] > ans.size() && i+j == dp[i][j]+n){
97 //s[i-dp[i][j]...i] = sr[j-dp[i][j]...j]
98 // cout << s.substr(i-dp[i][j], dp[i][j]) << ", " << rs.substr(j-dp[i][j], dp[i][j]) << endl;
99 ans = s.substr(i-dp[i][j], dp[i][j]);
100 }
101 }
102 }
103
104 return ans;
105 }
106};
107
108//same as above, space complexity O(n)
109//Runtime: 652 ms, faster than 10.41% of C++ online submissions for Longest Palindromic Substring.
110//Memory Usage: 14.5 MB, less than 40.00% of C++ online submissions for Longest Palindromic Substring.
111class Solution {
112public:
113 string longestPalindrome(string s) {
114 int n = s.size();
115 string rs(s.rbegin(), s.rend());
116 string ans = "";
117
118 vector<vector<int>> dp(2, vector(n+1, 0));
119
120 for(int i = 1; i <= n; i++){
121 for(int j = 1; j <= n; j++){
122 if(s[i-1] == rs[j-1]){
123 dp[i%2][j] = dp[(i+1)%2][j-1] + 1;
124 }else{
125 dp[i%2][j] = 0;
126 }
127
128 if(dp[i%2][j] > ans.size() && i+j == dp[i%2][j]+n){
129 ans = s.substr(i-dp[i%2][j], dp[i%2][j]);
130 }
131 }
132 }
133
134 return ans;
135 }
136};
137
138//Approach 4: Expand Around Center
139//Runtime: 84 ms, faster than 52.27% of C++ online submissions for Longest Palindromic Substring.
140//Memory Usage: 102.1 MB, less than 18.62% of C++ online submissions for Longest Palindromic Substring.
141//time: O(N^2), space: O(1)
142class Solution {
143public:
144 int expandAroundCenter(string s, int l, int r){
145 //s[l...r], both inclusive
146 while(l >= 0 && r < s.size() && s[l] == s[r]){
147 l--;
148 r++;
149 }
150
151 //return to previous valid status
152 l++; r--;
153
154 return r-l+1;
155 };
156
157 string longestPalindrome(string s) {
158 if(s.size() == 0) return "";
159 int start = 0, end = 0;
160 for(int i = 0; i < s.size(); i++){
161 int len1 = expandAroundCenter(s, i, i);
162 int len2 = expandAroundCenter(s, i, i+1);
163 int len = max(len1, len2);
164 // cout << "len: " << len1 << ", " << len2 << endl;
165 if(len > end-start+1){
166 /*
167 for odd len:
168 (len-1)/2 and len/2 are the same
169
170 for even len:
171 (len-1)/2 = len/2 -1,
172 i.e. [i-(x-1), i, i+1, i+x]
173 */
174 start = i - (len-1)/2;
175 end = i + len/2;
176 // cout << "[" << start << ", " << end << "]" << endl;
177 }
178 }
179 // cout << "================" << endl;
180 return s.substr(start, end-start+1);
181 }
182};
183
184//Approach 5: Manacher's Algorithm
185//https://www.youtube.com/watch?v=nbTSfrEfo6M&feature=emb_logo
186//Runtime: 8 ms, faster than 94.20% of C++ online submissions for Longest Palindromic Substring.
187//Memory Usage: 7.6 MB, less than 100.00% of C++ online submissions for Longest Palindromic Substring.
188//time: O(n), space: O(n)
189class Solution {
190public:
191 string longestPalindrome(string s) {
192 string t(1, '^');
193
194 for(int i = 0; i < s.size(); i++){
195 t += '#'; t += s[i];
196 }
197
198 t += '#'; t += '$';
199
200 // cout << t << endl;
201
202 vector<int> p(t.size(), 0);
203 int mirror = 0;
204 int center = 0;
205 int right = 0;
206 int maxStart = 0;
207
208 for(int i = 0; i < t.size(); i++){
209 //update mirror
210 mirror = 2 * center - i;
211
212 /*
213 only if current position < last palindrome's right boundary,
214 we can use the mirror property of that palindrome
215 */
216 if(i < right){
217 /*
218 p[i] is supposed to be same as p[mirror],
219 but it's also restricted by
220 the distance to the palindrome's right boundary(right-i)
221 */
222 p[i] = min(p[mirror], right - i);
223 }
224
225 /*
226 try to expand it:
227 try assume the new p[i] is 1+p[i], and see if it works
228
229 i+(1+p[i]) < t.size() && i-(1+p[i]) >= 0:
230 the expected new palindrome's range is [i-p[i],i+p[i]],
231 we need to check if it falls in [0, t.size())
232 */
233 while(i+(1+p[i]) < t.size() && i-(1+p[i]) >= 0 && t[i+(1+p[i])] == t[i-(1+p[i])]){
234 p[i]++;
235 }
236
237 //update ans
238 if(p[i] > p[maxStart]){
239 maxStart = i;
240 }
241
242 // cout << "i: " << i << ", center: " << center << ", mirror: " << mirror << ", p[i]: " << p[i] << endl;
243
244 /*
245 find a palindrome whose right boundary exceeds
246 the old palindrome's right boundary,
247 so update the variables "right" and "center" which
248 are related to palindrome
249 */
250 if(i+p[i] > right){
251 right = i+p[i];
252 center = i;
253 }
254 }
255
256 // cout << "i: " << maxStart << ", p[i]: " << p[maxStart] << endl;
257
258 return s.substr((maxStart-p[maxStart])/2, p[maxStart]);
259 }
260};Cost
Complexity
Time
O(N^2), space: O(N^2)
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.