The trick here is to name the state correctly, then let the implementation follow. For 1531. String Compression II, 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.
The notes already sitting in the source point us in the right direction:
- DP
- https://leetcode.com/problems/string-compression-ii/discuss/755970/Python-dynamic-programming
- TLE
- 63 / 132 test cases passed.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are counter, getLengthOfOptimalCompression.
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.
- 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(26*N^3), space: O(26*N^3)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//DP
02//https://leetcode.com/problems/string-compression-ii/discuss/755970/Python-dynamic-programming
03//TLE
04//63 / 132 test cases passed.
05class Solution {
06public:
07 int counter(string& s, int cur, char last_char, int last_count, int k){
08 if(cur == s.size()) return 0;
09
10 if(s[cur] == last_char){
11 /*
12 we only discard char when we first meet it,
13 so here we always keep the char
14 */
15 int incr = 0;
16 if(last_count == 1 || log10(last_count+1) == int(log10(last_count+1))){
17 /*
18 we need one more digit when the count changes from:
19 1->2, 9->10, 99->100
20 */
21 incr = 1;
22 }
23 int ret = incr + counter(s, cur+1, s[cur], last_count+1, k);
24 // cout << "(" << cur << ", " << last_char << ", " << last_count << ", " << k << ") : " << ret << endl;
25 return ret;
26 }else{
27 /*
28 when we meet first such char,
29 we can choose whether to keep it or discard it
30 */
31 //add 1: current char is the first char of its kind, and it takes one position in the encoded string
32 int keep_count = 1 + counter(s, cur+1, s[cur], 1, k);
33 //current char deleted, so last_char and last_count remain unchanged
34 //k < 0 is impossible, early stopping
35 int discard_count = (k >= 1) ? counter(s, cur+1, last_char, last_count, k-1) : numeric_limits<int>::max();
36
37 int ret = min(keep_count, discard_count);
38 // cout << "(" << cur << ", " << last_char << ", " << last_count << ", " << k << ") : " << ret << endl;
39 return ret;
40 }
41 };
42
43 int getLengthOfOptimalCompression(string s, int k) {
44 int n = s.size();
45
46 return counter(s, 0, '#', 0, k);
47 }
48};
49
50//DP with memorization
51//https://leetcode.com/problems/string-compression-ii/discuss/755762/C%2B%2B-top-down-dynamic-programming-with-explanation
52//TLE
53//87 / 132 test cases passed.
54//time: O(26*N^3), space: O(26*N^3)
55class Solution {
56public:
57 vector<vector<vector<vector<int>>>> memo;
58
59 int counter(string& s, int cur, char last_char, int last_count, int k){
60 if(cur == s.size()) return 0;
61
62 if(memo[cur][last_char-'a'][last_count][k] != -1){
63 return memo[cur][last_char-'a'][last_count][k];
64 }
65
66 if(s[cur] == last_char){
67 int incr = 0;
68 if(last_count == 1 || log10(last_count+1) == int(log10(last_count+1))){
69 incr = 1;
70 }
71 memo[cur][last_char-'a'][last_count][k] = incr + counter(s, cur+1, s[cur], last_count+1, k);
72 }else{
73 int keep_count = 1 + counter(s, cur+1, s[cur], 1, k);
74 int discard_count = (k >= 1) ? counter(s, cur+1, last_char, last_count, k-1) : numeric_limits<int>::max();
75
76 memo[cur][last_char-'a'][last_count][k] = min(keep_count, discard_count);
77 }
78
79 return memo[cur][last_char-'a'][last_count][k];
80 };
81
82 int getLengthOfOptimalCompression(string s, int k) {
83 int n = s.size();
84
85 memo = vector<vector<vector<vector<int>>>>(n, vector<vector<vector<int>>>(26+1, vector<vector<int>>(n, vector<int>(k+1, -1))));
86
87 //'{' is the char just after 'z'
88 return counter(s, 0, '{', 0, k);
89 }
90};
91
92//DP with memorization, prune
93//https://leetcode.com/problems/string-compression-ii/discuss/755762/C%2B%2B-top-down-dynamic-programming-with-explanation
94//Runtime: 1168 ms, faster than 22.58% of C++ online submissions for String Compression II.
95//Memory Usage: 450.5 MB, less than 5.12% of C++ online submissions for String Compression II.
96//time: O(26*10*N^2), space: O(26*10*N^2)
97class Solution {
98public:
99 vector<vector<vector<vector<int>>>> memo;
100
101 int counter(string& s, int cur, char last_char, int last_count, int k){
102 if(cur == s.size()) return 0;
103
104 if(memo[cur][last_char-'a'][last_count][k] != -1){
105 return memo[cur][last_char-'a'][last_count][k];
106 }
107
108 if(s[cur] == last_char){
109 int incr = 0;
110 if(last_count == 1 || last_count == 9){
111 incr = 1;
112 }
113 //set the upper limit of "last_count" as 10
114 memo[cur][last_char-'a'][last_count][k] = incr + counter(s, cur+1, s[cur], min(10, last_count+1), k);
115 }else{
116 int keep_count = 1 + counter(s, cur+1, s[cur], 1, k);
117 int discard_count = (k >= 1) ? counter(s, cur+1, last_char, last_count, k-1) : numeric_limits<int>::max();
118
119 memo[cur][last_char-'a'][last_count][k] = min(keep_count, discard_count);
120 }
121
122 return memo[cur][last_char-'a'][last_count][k];
123 };
124
125 int getLengthOfOptimalCompression(string s, int k) {
126 int n = s.size();
127
128 if(n == 100 && k == 0){
129 char c = s[0];
130 if(s == string(c, 100)){
131 /*
132 this is the only case that "last_count" could be 100,
133 and now we exclude it
134 */
135 return 4;
136 }
137 }
138
139 /*
140 now the max value "last_count" could be is 99,
141 and we know that when "last_count" is in [10,99],
142 the encoded string will have same length,
143 so we don't care "last_count" once it reaches 10
144 */
145
146 memo = vector<vector<vector<vector<int>>>>(n, vector<vector<vector<int>>>(26+1, vector<vector<int>>(11, vector<int>(k+1, -1))));
147
148 return counter(s, 0, '{', 0, k);
149 }
150};
151
152//DP with memorization, prune, use array instead of vector
153//https://leetcode.com/problems/string-compression-ii/discuss/755762/C%2B%2B-top-down-dynamic-programming-with-explanation
154//Runtime: 376 ms, faster than 45.89% of C++ online submissions for String Compression II.
155//Memory Usage: 19.2 MB, less than 49.55% of C++ online submissions for String Compression II.
156class Solution {
157public:
158 int memo[100][27][11][101];
159
160 int counter(string& s, int cur, char last_char, int last_count, int k){
161 if(cur == s.size()) return 0;
162
163 if(memo[cur][last_char-'a'][last_count][k] != -1){
164 return memo[cur][last_char-'a'][last_count][k];
165 }
166
167 if(s[cur] == last_char){
168 int incr = 0;
169 if(last_count == 1 || last_count == 9){
170 incr = 1;
171 }
172 memo[cur][last_char-'a'][last_count][k] = incr + counter(s, cur+1, s[cur], min(10, last_count+1), k);
173 }else{
174 int keep_count = 1 + counter(s, cur+1, s[cur], 1, k);
175 int discard_count = (k >= 1) ? counter(s, cur+1, last_char, last_count, k-1) : numeric_limits<int>::max();
176
177 memo[cur][last_char-'a'][last_count][k] = min(keep_count, discard_count);
178 }
179
180 return memo[cur][last_char-'a'][last_count][k];
181 };
182
183 int getLengthOfOptimalCompression(string s, int k) {
184 int n = s.size();
185
186 if(n == 100 && k == 0){
187 char c = s[0];
188 if(s == string(c, 100)){
189 /*
190 this is the only case that "last_count" could be 100,
191 and now we exclude it
192 */
193 return 4;
194 }
195 }
196
197 /*
198 now the max value "last_count" could be is 99,
199 and we know that when "last_count" is in [10,99],
200 the encoded string will have same length,
201 so we don't care "last_count" once it reaches 10
202 */
203
204 for(int a = 0; a < n; ++a){
205 for(int b = 0; b <= 26; ++b){
206 for(int c = 0; c <= 10; ++c){
207 for(int d = 0; d <= n; ++d){
208 memo[a][b][c][d] = -1;
209 }
210 }
211 }
212 }
213
214 return counter(s, 0, '{', 0, k);
215 }
216};Cost
Complexity
Time
O(26*N^3), space: O(26*N^3)
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.