This problem looks busy at first, but the accepted solution is built around one steady invariant. For 132. Palindrome Partitioning II, the solution in this repository is mainly a heap / priority queue 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: heap / priority queue, dynamic programming, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- Recursive
- TLE
- 21 / 29 test cases passed.
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 isPalindrome, minCut, available.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- 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.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
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//Recursive
02//TLE
03//21 / 29 test cases passed.
04class Solution {
05public:
06 bool isPalindrome(string s){
07 int n = s.size();
08 for(int i = 0; i < s.size()/2; i++){
09 if(s[i] != s[n-1-i]) return false;
10 }
11 return true;
12 };
13
14 int minCut(string s) {
15 int ans = 0;
16 if(!isPalindrome(s)){
17 // cout << s << endl;
18 if(s.size() == 2) return 1;
19 ans = INT_MAX;
20 for(int i = 1; i < s.size(); i++){
21 ans = min(ans, minCut(s.substr(0, i)) + minCut(s.substr(i)));
22 }
23 ans++;
24 }
25 return ans;
26 }
27};
28
29//DP
30//WA
31//28 / 29 test cases passed.
32class Solution {
33public:
34 int minCut(string s) {
35 int n = s.size();
36 if(n == 0 || n == 1) return 0;
37
38 vector<vector<int>> dp(n, vector(n, 0));
39 vector<priority_queue<int, vector<int>>> widths(n);
40
41 for(int w = 1; w <= n; w++){
42 for(int start = 0; start+w-1 < n; start++){
43 int end = start+w-1;
44 if(w == 1)dp[start][end] = true;
45 else if(w == 2)dp[start][end] = (s[start] == s[end]);
46 else dp[start][end] = (dp[start+1][end-1] && s[start] == s[end]);
47
48 if(dp[start][end]) widths[start].push(w);
49 }
50 }
51
52 // for(int i = 0; i < n; i++){
53 // cout << maxWidths[i] << " ";
54 // }
55 // cout << endl;
56
57 int cursor = 0;
58 int ans = 0;
59
60 //how many segments
61 // WA when "aaabaa"
62 // while(cursor < n){
63 // cursor = cursor + maxWidths[cursor];
64 // ans++;
65 // }
66
67 priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
68 for(int i = 0; i < n; i++){
69 pq.push(make_pair(widths[i].top(), i));
70 }
71
72 // queue<vector<int>> segments;
73 // vector<int> segment;
74 // segments.push({0, n-1});
75 int start, end;
76 vector<bool> available(n, true);
77
78 while(!pq.empty() && any_of(available.begin(), available.end(), [](bool b){return b;})){
79 // segment = segments.front();
80 // start = segment[0];
81 // end = segment[1];
82 /*
83 greedily choose the segment with longest width,
84 this may be the reason of WA
85 */
86 pair<int, int> p = pq.top(); pq.pop();
87 start = p.second;
88 end = start+p.first-1;
89
90 // cout <<"[" << start << ", " << end << "]: " << s.substr(start, end-start+1) << endl;
91
92 bool valid = true;
93 for(int i = start; i <= end; i++){
94 if(!available[i]){
95 valid = false;
96 break;
97 }
98 }
99
100 if(!valid){
101 widths[start].pop();
102 if(!widths[start].empty()) pq.push(make_pair(widths[start].top(), start));
103 continue;
104 }
105
106 // cout <<"[" << start << ", " << end << "]: " << s.substr(start, end-start+1) << endl;
107
108 for(int i = start; i <= end; i++){
109 available[i] = false;
110 }
111
112 ans++;
113 }
114
115 //how many cuts
116 return ans-1;
117 }
118};
119
120//DP, start from center
121//https://leetcode.com/problems/palindrome-partitioning-ii/discuss/42198/My-solution-does-not-need-a-table-for-palindrome-is-it-right-It-uses-only-O(n)-space./112629
122//Runtime: 12 ms, faster than 88.70% of C++ online submissions for Palindrome Partitioning II.
123//Memory Usage: 6.3 MB, less than 100.00% of C++ online submissions for Palindrome Partitioning II.
124class Solution {
125public:
126 int minCut(string s) {
127 int n = s.size();
128 if(n <= 1) return 0;
129
130 vector<int> dp(n);
131 iota(dp.begin(), dp.end(), 0);
132
133 int w, choice;
134 //start from center = 1, because dp[0] is always 0
135 for(int c = 1; c < n; c++){
136 w = 0;
137 //odd
138 //c-w: left, c+w: right
139 while(c-w >= 0 && c+w < n && s[c-w] == s[c+w]){
140 //c-w-1: left-1
141 choice = (c-w-1 >= 0) ? dp[c-w-1]+1 : 0;
142 //update dp[end], not dp[center]!
143 dp[c+w] = min(dp[c+w], choice);
144 w++;
145 }
146
147 //even
148 w = 0;
149
150 /*
151 since we start from c = 1,
152 we need to take care of s[0],
153 so we set left = c-w-1 and right = c+w,
154 not left = c-w and right = c+w+1
155 */
156 while(c-w-1 >= 0 && c+w < n && s[c-w-1] == s[c+w]){
157 choice = (c-w-1-1 >= 0) ? dp[c-w-1-1]+1 : 0;
158 dp[c+w] = min(dp[c+w], choice);
159 w++;
160 }
161 }
162
163 return dp[n-1];
164 }
165};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.