The trick here is to name the state correctly, then let the implementation follow. For 1147. Longest Chunked Palindrome Decomposition, 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, greedy.
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 longestDecomposition, power.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- 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:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
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: 4 ms, faster than 88.52% of C++ online submissions for Longest Chunked Palindrome Decomposition.
02//Memory Usage: 10.1 MB, less than 100.00% of C++ online submissions for Longest Chunked Palindrome Decomposition.
03class Solution {
04public:
05 int longestDecomposition(string text) {
06 int start = 0, N = text.size();
07 int ans = 0;
08
09 // cout << "N: " << N << endl;
10
11 /*
12 for even N, say 4, start should be in [0,1]
13 for odd N, say 3, start should be in [0,1] (the middle element should also be start once)
14 */
15 while(start < (N+1)/2){
16 int width = 1;
17 /*
18 current substring ends at start+width-1,
19 for odd N, say 3, ends at 0 or 1
20 for even N, say 4, ends at 0 or 1
21 */
22 while(start + width < (N+1)/2 &&
23 text.substr(start, width) != text.substr(N-start-width, width)){
24 // cout << width <<" "<< text.substr(start, width) << " " << text.substr(N-start-width, width) << endl;
25 width++;
26 }
27 // cout << width <<" "<< text.substr(start, width) << " " << text.substr(N-start-width, width) << endl;
28
29 /*
30 if start + width >= (N+1)/2, that means current substring ends at the middle for odd N (or just before the middle for even N)
31 */
32 if((text.substr(start, width) == text.substr(N-start-width, width)) && (start != N-start-width)){
33 //the two parts are the same and they are different part in original string
34 //tokens in both ends
35 ans+=2;
36 }else{
37 //we come to half
38 // cout << start << " " << width << " " << N/2 <<endl;
39 ans++;
40 }
41
42 start += width;
43 }
44
45 return ans;
46 }
47};
48
49//Rolling hash, Rabin Karp algorithm, two pointer
50//https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/350711/Close-to-O(n)-Python-Rabin-Karp-Algorithm-with-two-pointer-technique-with-explanation-(~40ms)
51//Runtime: 4 ms, faster than 88.66% of C++ online submissions for Longest Chunked Palindrome Decomposition.
52//Memory Usage: 6.6 MB, less than 81.82% of C++ online submissions for Longest Chunked Palindrome Decomposition.
53class Solution {
54public:
55 int power(int x, unsigned int y, unsigned int m){
56 if (y == 0)
57 return 1;
58 long long p = power(x, y/2, m) % m;
59 p = (p * p) % m;
60
61 return (y%2 == 0)? p : (x * p) % m;
62 };
63
64 int longestDecomposition(string text) {
65 int magic_prime = 107;
66 int low = 0, high = text.size()-1;
67 int cur_low_hash = 0, cur_high_hash = 0, cur_hash_length = 0;
68 int ans = 0;
69
70 while(low < high){
71 /*
72 construct a substring from the beginning by appending text[low],
73 and cur_low_hash is its hash value,
74 note that the newest char has smallest multiplier
75 */
76 cur_low_hash = (cur_low_hash * 26)%magic_prime;
77 cur_low_hash += (text[low]-'a');
78 cur_low_hash %= magic_prime;
79
80 //pow(26, cur_hash_length) cannot give corrent result even if using long long int in C++
81 /*
82 construct a substring from the end by appending text[high],
83 and cur_high_hash is its hash value,
84 note that the newest char has largest multiplier
85 */
86 cur_high_hash += (text[high]-'a')*(power(26, cur_hash_length, magic_prime));
87 cur_high_hash %= magic_prime;
88
89 //move the two pointers
90 low++;
91 high--;
92 //the length of the substring represented by cur_low_hash and cur_high_hash
93 cur_hash_length++;
94
95 /*
96 first compare the two substrings' hash values,
97 if they are equal, then compare the two substrings themselves
98 */
99 if(cur_low_hash == cur_high_hash && text.substr(low-cur_hash_length, cur_hash_length) == text.substr(high+1, cur_hash_length)){
100 //found two more groups
101 ans += 2;
102 //reset the states
103 cur_low_hash = 0;
104 cur_high_hash = 0;
105 cur_hash_length = 0;
106 }
107 }
108
109 //edge case 1: only leave a char in the middle(odd N)
110 //edge case 2: cannot find palindrome pair on two sides of the middle(even N)
111 if((cur_hash_length == 0 && low == high) || cur_hash_length > 0){
112 ans++;
113 }
114
115 return ans;
116 }
117};
118
119//DP
120//https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/351919/Java-DP-Solution.-Straight-Forward-With-Explanation
121//Runtime: 600 ms, faster than 5.44% of C++ online submissions for Longest Chunked Palindrome Decomposition.
122//Memory Usage: 461.4 MB, less than 100.00% of C++ online submissions for Longest Chunked Palindrome Decomposition.
123class Solution {
124public:
125 int longestDecomposition(string text) {
126 int N = text.size();
127 //dp[i]: max number of palindrome decompositions that s[0:i] + s[len-i:len] can form, not counting the strings between [i+1:len-i-1].
128 vector<int> dp(N/2+1, 0);
129 int ans = 0;
130 for(int r = 0; r < N/2; r++){
131 for(int l = 0; l <= r; l++){
132 /*
133 [l,r] is all possible substrings formed by the former part of text
134 for odd N, the middle char is not included
135 */
136 // cout << l << " " << r << endl;
137 //compare [l,r] and [N-r-1,N-l-1]
138 //dp[l] != 0: [0,l-1] must be valid so we can construct dp[r+1] upon it
139 //dp[0] is always valid
140 if(text.substr(l, r-l+1) == text.substr(N-r-1, r-l+1) &&
141 (l == 0 || dp[l] != 0)){
142 //dp[r+1] for s[0:r]
143 //dp[l] for s[0:l-1]
144 //dp[r+1] is for [0,r], and we are calculate it from [0,l-1] and [l,r]
145 //[l,r] is the current substring
146 //dp[l] is for [0,l-1], which is all chars before current substring
147 //dp[r+1] is equal to dp[l] plus current 2 tokens
148 // cout << r << " " << l-1 << " " << text.substr(l, r-l+1) << endl;
149 dp[r+1] = max(dp[r+1], dp[l]+2);
150 //ans: we can find "ans" palindromes from [0:r] and [N-1-r:N-1]
151 //dp[r+1] can be 0 if r is not the end of any palindrome, so we need a max function here
152 // ans = max(ans, dp[l]+2);
153 ans = max(ans, dp[r+1]);
154 }
155 }
156 }
157
158 // for(int i = 0; i < dp.size(); i++){
159 // if(dp[i] > 0) cout << "i: " << i << ", " << dp[i] << endl;
160 // }
161
162 //((N % 2 == 0) && dp[N/2] != 0): the string's length is even and there is a palindrome ends just before the middle point
163 return ((N % 2 == 0) && dp[N/2] != 0) ? dp[N/2] : ans+1;
164 }
165};
166
167//Greedy, brute force
168//https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/350560/JavaC%2B%2BPython-Easy-Greedy-with-Prove
169//Runtime: 4 ms, faster than 88.52% of C++ online submissions for Longest Chunked Palindrome Decomposition.
170//Memory Usage: 10.8 MB, less than 100.00% of C++ online submissions for Longest Chunked Palindrome Decomposition.
171//time: O(N) * O(string), space O(N)
172class Solution {
173public:
174 int longestDecomposition(string text) {
175 int ans = 0, N = text.size();
176 string l = "", r = "";
177 for(int i = 0; i < N; i++){
178 l += text[i];
179 r = text[N-i-1] + r;
180 /*
181 "ghiabcdefhelloadamhelloabcdefghi"
182 the character in the middle can also be processed correctly
183 2 ghi
184 8 abcdef
185 13 hello
186 17 adam
187 22 hello
188 28 abcdef
189 31 ghi
190 */
191 if(l == r){
192 // cout << i << " " << l << endl;
193 l = "";
194 r = "";
195 ans++;
196 }
197 }
198 return ans;
199 }
200};
201
202//Greedy, tail recursion
203//https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/350560/JavaC%2B%2BPython-Easy-Greedy-with-Prove
204//Runtime: 4 ms, faster than 88.52% of C++ online submissions for Longest Chunked Palindrome Decomposition.
205//Memory Usage: 10.7 MB, less than 100.00% of C++ online submissions for Longest Chunked Palindrome Decomposition.
206class Solution {
207public:
208 int longestDecomposition(string text, int res = 0) {
209 int n = text.length();
210 //l is 1-based
211 for (int l = 1; l <= n / 2; ++l){
212 //this if is just for speed up
213 if (text[0] == text[n - l] && text[l - 1] == text[n - 1]){
214 if (text.substr(0, l) == text.substr(n - l)){
215 // cout << l << " " << text.substr(0, l) << endl;
216 //remove current palindrome from text
217 return longestDecomposition(text.substr(l, n - l - l), res + 2);
218 }
219 }
220 }
221 /*
222 the recursion ends when:
223 1. we cannot find any palindrome for text(res + 1)
224 2. text's length is 0(res)
225 */
226 // cout << "n: " << n << endl;
227 return n ? res + 1 : res;
228 }
229};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.