I like to read this solution as a small machine: keep the useful information, throw away the noise. For 647. Palindromic Substrings, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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, sliding window.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are countSubstrings, join, manachers.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- 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) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 24 ms, faster than 32.32% of C++ online submissions for Palindromic Substrings.
02//Memory Usage: 21.9 MB, less than 12.00% of C++ online submissions for Palindromic Substrings.
03class Solution {
04public:
05 int countSubstrings(string s) {
06 int N = s.size();
07 vector<vector<int>> dp(N, vector<int>(N, 0));
08 int ans = 0;
09
10 //width 1
11 //each char is a palindrome itself
12 for(int i = 0; i < N; i++){
13 dp[i][i] = 1;
14 ans++;
15 }
16
17 for(int width = 2; width <= N; width++){
18 for(int start = 0; start + width -1 < N; start++){
19 int end = start + width -1;
20 //if its substring is not valid, then it's not valid
21 if(start+1 <= end-1 && !dp[start+1][end-1]){
22 dp[start][end] = false;
23 continue;
24 }
25 dp[start][end] = (s[start] == s[end]);
26 if(dp[start][end]){
27 // cout << start << " " << end << endl;
28 ans++;
29 }
30 }
31 }
32
33 return ans;
34 }
35};
36
37//DP
38//Runtime: 24 ms, faster than 40.82% of C++ online submissions for Palindromic Substrings.
39//Memory Usage: 20.4 MB, less than 12.00% of C++ online submissions for Palindromic Substrings.
40class Solution {
41public:
42 int countSubstrings(string s) {
43 int n = s.size();
44 /*
45 padding 0 and n+1,
46 used for dp[l+1][r-1]
47 */
48 vector<vector<int>> dp(n+2, vector<int>(n+2, 0));
49 int ans = 0;
50
51 //valid range is [1...n]
52 for(int l = n; l >= 1; l--){
53 for(int r = l; r <= n; r++){
54 /*
55 l and r is 1-based,
56 need to convert them to 0-based to index s
57 */
58 /*
59 l+1 >= r-1 : s[l+1...r-1] will always be palindrome
60 */
61 if((l+1 >= r-1 || dp[l+1][r-1] != 0) && s[l-1] == s[r-1]){
62 dp[l][r] = 1; //dp[l+1][r-1]+1;
63 // cout << l << ", " << r << ", " << dp[l][r] << endl;
64 ans += dp[l][r];
65 }else{
66 dp[l][r] = 0;
67 }
68 }
69 }
70
71 return ans;
72 }
73};
74
75//DP, O(N) space
76//Runtime: 12 ms, faster than 60.81% of C++ online submissions for Palindromic Substrings.
77//Memory Usage: 6.4 MB, less than 100.00% of C++ online submissions for Palindromic Substrings.
78class Solution {
79public:
80 int countSubstrings(string s) {
81 int n = s.size();
82 vector<int> dp(n+2, 0);
83 int ans = 0;
84
85 for(int l = n; l >= 1; l--){
86 //note taht we have changed the r to reverse order!
87 for(int r = n; r >= l; r--){
88 /*
89 dp[r-1] is dp[l+1][r-1] in previous method,
90 so we want dp[r-1] to be updated after dp[r],
91 so that dp[r-1] means dp[l+1][r-1], not dp[l][r-1]
92 */
93 if((l+1 >= r-1 || dp[r-1] != 0) && s[l-1] == s[r-1]){
94 dp[r] = 1;
95 ans += dp[r];
96 }else{
97 dp[r] = 0;
98 }
99 }
100 }
101
102 return ans;
103 }
104};
105
106//center expansion
107//https://leetcode.com/problems/palindromic-substrings/discuss/105687/Python-Straightforward-with-Explanation-(Bonus-O(N)-solution)
108//O(N^2)
109class Solution {
110public:
111 int countSubstrings(string s) {
112 int n = s.size();
113 int ans = 0;
114
115 //center could be n char of s and also n-1 spaces between chars
116 for(int center = 0; center < 2*n-1; center++){
117 //center = 0(0th char) -> left: 0, right: 0
118 //center = 1(btw 0th and 1st char) -> left: 0, right: 1
119 //center = 5(btw 2nd and 3rd char) -> left: 2, right: 3
120 int left = center/2;
121 int right = center/2 + center%2;
122
123 while(left >= 0 && right < n && s[left] == s[right]){
124 ans++;
125 left--;
126 right++;
127 }
128 }
129
130 return ans;
131 }
132};
133
134//Manacher’s Algorithm
135//https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-4/
136//https://leetcode.com/problems/palindromic-substrings/discuss/105687/Python-Straightforward-with-Explanation-(Bonus-O(N)-solution)
137//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Palindromic Substrings.
138//Memory Usage: 6.6 MB, less than 100.00% of C++ online submissions for Palindromic Substrings.
139//time: O(N)
140class Solution {
141public:
142 vector<int> L;
143
144 template <typename Iter>
145 std::string join(Iter begin, Iter end, std::string const& separator)
146 {
147 std::ostringstream result;
148 result.precision(2); //for floating point
149 if (begin != end)
150 result << *begin++;
151 while (begin != end)
152 //std::fixed : for floating point
153 result << std::fixed << separator << *begin++;
154 return result.str();
155 }
156
157 void manachers(string s){
158 s = join(s.begin(), s.end(), "#");
159 s = "^#" + s + "#$";
160 L = vector<int>(s.size(), 0);
161 int C = 0, R = 0;
162 //from first # to last #
163 //i: currentRightPosition
164 for(int i = 1; i < s.size()-1; i++){
165 if(R - i > 0){
166 L[i] = min(L[2*C-i], R-i);
167 }
168 while(s[i-L[i]-1] == s[i+L[i]+1]){
169 L[i]++;
170 }
171 if(R < i + L[i]){
172 R = i + L[i];
173 C = i;
174 }
175 }
176 };
177
178 int countSubstrings(string s) {
179 manachers(s);
180 int ans = 0;
181 for(int l : L){
182 ans += (1+l)/2;
183 }
184 return ans;
185 }
186};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
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.