Log inSign up
hardleetcodeNot Started

String Compression II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Run-length encoding is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "aabccc" we replace "aa" by "a2" and replace "ccc" by "c3". Thus the compressed string becomes "a2bc3".

Notice that in this problem, we are not adding '1' after single characters.

Given a string s and an integer k. You need to delete at most k characters from s such that the run-length encoded version of s has minimum length.

Find the *minimum length of the run-length encoded version of* s *after deleting at most* k *characters*.

Example 1 · Example:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting gives "a3bc3d" of length 6. Deleting "b" and "d" gives "a3c3" of length 4.

Example 2 · Example:

Input: s = "aabbaa", k = 2
Output: 2
Explanation: If we delete both "b"s, the remaining string is "aaaa" which compresses to "a4" of length 2.

Example 3 · Example:

Input: s = "aaaaaaaaaaa", k = 0
Output: 3
Explanation: Since k = 0, we cannot delete. "aaaaaaaaaaa" compresses to "a11" of length 3.

Constraints:

  • 1 <= s.length <= 100
  • 0 <= k <= s.length
  • s contains only lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Design 2D suffix grouping DP states for run-length compression.
  • Calculate length increments for character run counts.
  • Formulate branch choices: delete anchor character vs group anchor character forward.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Minimizing encoded string length with a deletion budget.
  • Grouping identical non-adjacent characters by removing obstacles.

Algorithmic Decision Tree:

  • Suffix Partition Dynamic Programming
  • Run-Length Encoding State Compression

Connected Patterns:

String CompressionEdit DistanceDelete Operation for Two Strings

1. 4D Memoized State DP

Intuition

Define dp(i, k, lastChar, count): option 1 is deleting s[i] (dp(i + 1, k - 1, lastChar, count)). Option 2 is keeping s[i]: if s[i] == lastChar, the cost increases if count transitions 1->2, 9->10, or 99->100. If s[i] != lastChar, cost increases by 1 for the new character.

When to apply: Direct state formulation.

Algorithm

  1. Initialize 4D memo table.
  2. Helper solve(i, k, lastChar, count):
  3. If k < 0: return infinity.
  4. If i == s.length: return 0.
  5. Option 1 (delete s[i]): res = solve(i + 1, k - 1, lastChar, count).
  6. Option 2 (keep s[i]): compute length delta and recurse solve(i + 1, k, s[i], newCount).
  7. Return minimum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5#include <cstring>
6
7class Solution {
8 int memo[105][105][27][105];
9 int solve(int i, int k, int lastChar, int count, const std::string& s) {
10 if (k < 0) return 1e9;
11 if (i == (int)s.size()) return 0;
12 if (memo[i][k][lastChar][count] != -1) return memo[i][k][lastChar][count];
13
14 // Option 1: Delete s[i]
15 int res = solve(i + 1, k - 1, lastChar, count, s);
16
17 // Option 2: Keep s[i]
18 int curChar = s[i] - 'a' + 1;
19 if (curChar == lastChar) {
20 int inc = (count == 1 || count == 9 || count == 99) ? 1 : 0;
21 res = std::min(res, inc + solve(i + 1, k, lastChar, count + 1, s));
22 } else {
23 res = std::min(res, 1 + solve(i + 1, k, curChar, 1, s));
24 }
25
26 return memo[i][k][lastChar][count] = res;
27 }
28public:
29 int getLengthOfOptimalCompression(std::string s, int k) {
30 std::memset(memo, -1, sizeof(memo));
31 return solve(0, k, 0, 0, s);
32 }
33};
34
35int main() {
36 Solution sol;
37 std::cout << sol.getLengthOfOptimalCompression("aaabcccd", 2) << std::endl; // 4
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N * K * 26 * N) — State space size: 100 * 100 * 27 * 100.
  • Space complexity: O(N * K * 26 * N)

Why Brute Force Doesn't Scale:

Anchor-based forward grouping reduces state space from 4D to 2D.

Compact O(N * K) memoization table.

2. Bottom-Up 2D Dynamic Programming (i, k)

Intuition

Define dp[i][k] as min compressed length of s[i...] with k deletions. Initialize dp[N][k] = 0. For i from N - 1 down to 0: if k > 0, dp[i][k] = dp[i + 1][k - 1]. Scan j from i to N - 1, counting matches s[j] == s[i] and mismatch deletions. If del <= k: dp[i][k] = min(dp[i][k], encodedLen(cnt) + dp[j + 1][k - del]).

When to apply: Non-recursive bottom-up implementation.

Algorithm

  1. Initialize dp[N + 1][k + 1] with infinity.
  2. dp[N][k] = 0 for all k.
  3. Iterate i from N - 1 down to 0:
  4. Iterate remK from 0 to k:
  5. If remK > 0: dp[i][remK] = dp[i + 1][remK - 1].
  6. same = 0, diff = 0.
  7. For j from i to N - 1:
  8. If s[j] == s[i]: same++.
  9. Else: diff++.
  10. If diff > remK: break.
  11. len = 1 + (same >= 100 ? 3 : same >= 10 ? 2 : same >= 2 ? 1 : 0).
  12. dp[i][remK] = min(dp[i][remK], len + dp[j + 1][remK - diff]).
  13. Return dp[0][k].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7 int getLen(int count) {
8 if (count == 1) return 1;
9 if (count < 10) return 2;
10 if (count < 100) return 3;
11 return 4;
12 }
13public:
14 int getLengthOfOptimalCompression(std::string s, int k) {
15 int n = s.size();
16 std::vector<std::vector<int>> dp(n + 1, std::vector<int>(k + 1, 1e9));
17
18 for (int remK = 0; remK <= k; ++remK) dp[n][remK] = 0;
19
20 for (int i = n - 1; i >= 0; --i) {
21 for (int remK = 0; remK <= k; ++remK) {
22 if (remK > 0) {
23 dp[i][remK] = dp[i + 1][remK - 1];
24 }
25 int same = 0, diff = 0;
26 for (int j = i; j < n; ++j) {
27 if (s[j] == s[i]) same++;
28 else diff++;
29
30 if (diff > remK) break;
31
32 dp[i][remK] = std::min(dp[i][remK], getLen(same) + dp[j + 1][remK - diff]);
33 }
34 }
35 }
36 return dp[0][k];
37 }
38};
39
40int main() {
41 Solution sol;
42 std::cout << sol.getLengthOfOptimalCompression("aaabcccd", 2) << std::endl; // 4
43 std::cout << sol.getLengthOfOptimalCompression("aabbaa", 2) << std::endl; // 2
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N^2 * K) — State space of N * K, each doing an O(N) forward scan.
  • Space complexity: O(N * K)

3. Memoized 2D Suffix DP (Optimal)

Intuition

Define solve(i, k) returning the minimum compressed length for s[i...] with k deletions. Base cases: k < 0 returns infinity, n - i <= k returns 0 (can delete all remaining characters). At state (i, k): 1. Delete s[i]: res = solve(i + 1, k - 1). 2. Keep s[i]: scan j from i to n - 1, counting same = (s[j] == s[i]) and diff = (s[j] != s[i]). As long as diff <= k, transition res = min(res, encodedLen(same) + solve(j + 1, k - diff)). Memoize memo[i][k].

When to apply: The standard gold standard solution.

Algorithm

  1. Initialize memo[N][K + 1] with -1.
  2. Helper solve(i, k):
  3. If k < 0: return infinity.
  4. If n - i <= k: return 0.
  5. If memo[i][k] != -1: return memo[i][k].
  6. res = solve(i + 1, k - 1) (delete s[i]).
  7. same = 0, diff = 0.
  8. For j from i to n - 1:
  9. If s[j] == s[i]: same++.
  10. Else: diff++.
  11. If diff > k: break.
  12. len = 1 + (same >= 100 ? 3 : same >= 10 ? 2 : same >= 2 ? 1 : 0).
  13. res = min(res, len + solve(j + 1, k - diff)).
  14. Return memo[i][k] = res.

Run-Length DP with Optimal Deletion Budgeting

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [a, a, a, b, c, c, c, d]
Current operationSTEP 1 OF 6
Observation: Without deletions, "aaabcccd" compresses to "a3bc3d" (length 6)
Visual state
Values and pointers at this exact step
array
S
a
a
a
b
c
c
c
d
0
1
2
3
↑ Candidate delete 1: 'b'
4
5
6
7
↑ Candidate delete 2: 'd'
Variables at this step
k
2
budget
2
uncompressedRunLength
a3bc3d (len 6)
Why this step matters

Observation: Without deletions, "aaabcccd" compresses to "a3bc3d" (length 6). Budget k = 2 deletions.

Decision: Isolated characters 'b' and 'd' each cost 1 character slot. Deleting both consumes exactly k = 2 deletions.

Invariant: Optimal compression strategically removes singletons and decreases multi-digit run powers.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7 int memo[105][105];
8 int getLen(int count) {
9 if (count == 1) return 1;
10 if (count < 10) return 2;
11 if (count < 100) return 3;
12 return 4;
13 }
14
15 int solve(int i, int k, const std::string& s) {
16 if (k < 0) return 1e9;
17 int n = s.size();
18 if (n - i <= k) return 0;
19 if (memo[i][k] != -1) return memo[i][k];
20
21 // Option 1: Delete s[i]
22 int res = solve(i + 1, k - 1, s);
23
24 // Option 2: Keep s[i] as run leader
25 int same = 0, diff = 0;
26 for (int j = i; j < n; ++j) {
27 if (s[j] == s[i]) same++;
28 else diff++;
29
30 if (diff > k) break;
31
32 res = std::min(res, getLen(same) + solve(j + 1, k - diff, s));
33 }
34
35 return memo[i][k] = res;
36 }
37public:
38 int getLengthOfOptimalCompression(std::string s, int k) {
39 for (int i = 0; i <= (int)s.size(); ++i) {
40 for (int j = 0; j <= k; ++j) {
41 memo[i][j] = -1;
42 }
43 }
44 return solve(0, k, s);
45 }
46};
47
48int main() {
49 Solution sol;
50 std::cout << sol.getLengthOfOptimalCompression("aaabcccd", 2) << std::endl; // 4
51 std::cout << sol.getLengthOfOptimalCompression("aabbaa", 2) << std::endl; // 2
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(N^2 * K) — N * K subproblems, each evaluating at most N forward transitions.
  • Space complexity: O(N * K) memo table

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.4D Memoized State DP (i, k, lastChar, lastCount)O(N * K * 26 * N)O(N * K * 26 * N)Directly encodes trailing run state.High state space dimension.
2.2D Memoized Suffix Grouping DP (Optimal)OptimalO(N^2 * K)O(N * K)Compact 2D state space (i, k) by grouping identical characters forward.Requires inner loop forward scan up to N.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Assuming run-length encoding includes 1 for count 1 (problem explicitly notes a is length 1, not a1).

Pitfall 2:

Missing count transitions where a10 takes 3 chars and a100 takes 4 chars.

Crucial Edge Cases to Validate:

  • k >= s.length: All characters deleted -> compressed length 0.
  • k == 0 (no deletions allowed): Computes standard run-length encoded length directly.
  • Count crossing 10 or 100 boundary: getLen() accurately accounts for single digit vs multi-digit encoding lengths.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify encoding rules: single character has length 1 (e.g. a), 2-9 has length 2 (e.g. a9), 10-99 has length 3 (e.g. a10).
  2. Explain how the anchor approach elegantly groups non-adjacent matching characters by spending deletion tokens on obstacles.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does 2D DP on (i, k) suffice instead of tracking the previous character?

Back to DSA Sheet