String Compression II solution and explanation
Google
9 more videos on this problem
String Compression II - Leetcode 1531 - PythonNeetCodeIO · 19:43 · 34K views
String Compression II | Recursion | Memo | Leetcode 1531codestorywithMIK · 41:53 · 8K views
LeetCode 1531. String Compression IIHappy Coding · 36:50 · 7K views
1531. String Compression II | 3 Ways | DP-HARDAryan Mittal · 45:46 · 5K views
Leetcode 1531 String Compression II | Coding Decoded SDE SheetCoding Decoded · 20:03 · 5K views
Daily Leetcode #928: Oct 15, 2022 - 1531. String Compression IIProgramming Live with Larry · 34:35 · 2K views
1531. String Compression II (Leetcode Hard)Programming Live with Larry · 52:11 · 1K views
String Compression II | LeetCode 1531 | Java 100% 19ms Solution | @LearnOverflowLearn Overflow · 21:59 · 1K views
Leetcode 1531 String Compression IIJeevan Kumar - Cracckify · 19:01 · 1K views
Leetcode Daily | 1531. String Compression IIcodingMohan · 35:09 · 1K views
The problem
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:
Input: s = "aaabcccd", k = 2 Output: 4 Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.
Example 2:
Input: s = "aabbaa", k = 2 Output: 2 Explanation: If we delete both 'b' characters, the resulting compressed string would be "a4" of length 2.
Example 3:
Input: s = "aaaaaaaaaaa", k = 0 Output: 3 Explanation: Since k is zero, we cannot delete anything. The compressed string is "a11" of length 3.
Constraints:
1 <= s.length <= 1000 <= k <= s.lengthscontains only lowercase English letters.
Approach overview
Problem Overview: Given a string s and an integer k, delete at most k characters so the run-length encoded (RLE) version of the remaining string is as short as possible. The challenge is that removing characters can merge groups or reduce digit counts in the compression length.
Approach 1: Dynamic Programming with Subproblems (O(n2 * k) time, O(n * k) space)
This problem fits naturally into dynamic programming. Define dp[i][k] as the minimum compressed length achievable starting at index i with k deletions remaining. From position i, iterate forward and try forming a group where s[i] is the kept character. Track the frequency of s[i] and count how many other characters must be deleted to maintain a continuous run. As the run grows, the encoded length increases only when the count crosses thresholds (1→2, 9→10, 99→100). For each extension, recursively compute the optimal result for the remainder of the string. Memoization avoids recomputing overlapping states. This approach systematically evaluates all valid compression segments while respecting the deletion budget.
Approach 2: Greedy Algorithm with Counting (O(n2) time, O(1) space)
A more heuristic approach scans segments and greedily keeps the most frequent character within a window while deleting others to form a longer run. Maintain a frequency counter while expanding a window from index i. The idea is to keep the character that appears most often and treat other characters as deletions. This reduces fragmentation in the compressed output because longer runs produce shorter RLE encodings. While expanding, compute how many deletions are required and stop when the budget is exceeded. The encoded length is derived from the run length using the same digit thresholds used in string compression. This strategy is simpler to implement but does not always guarantee optimality for every configuration.
Recommended for interviews: The dynamic programming solution is what interviewers expect. It demonstrates strong reasoning about compression boundaries, deletion tradeoffs, and optimal substructure. The greedy counting idea can help you reason about why grouping characters reduces encoded size, but the DP formulation is the reliable optimal solution for this hard problem.
Approach 1: Approach 1: Dynamic Programming with Subproblems
This approach uses dynamic programming to minimize the length of the compressed string after removing up to k characters. We'll iteratively decide for each position in the string whether to remove the character or keep it, and if kept, determine the optimal compression length.
The idea is to use a DP table where dp[i][j] stores the minimal compression length achievable for the substring s[0...i] with j deletions.
import math
def compress_length(c):
if c == 0:
return 0
if c == 1:
return 1
if c < 10:
return 2
if c < 100:
return 3
return 4
def min_length(s, k):
n = len(s)
dp = [[math.inf] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
for j in range(k + 1):
if dp[i][j] == math.inf:
continue
count = 0
for l in range(i, n):
if s[l] == s[i]:
count += 1
need_delete = l - i + 1 - count
if j + need_delete <= k:
dp[l + 1][j + need_delete] = min(dp[l + 1][j + need_delete], dp[i][j] + compress_length(count))
return min(dp[n])
if __name__ == "__main__":
s = "aaabcccd"
k = 2
print(min_length(s, k))import java.util.Arrays;
public class StringCompression {
private static int compressLength(int count) {
if (count == 0) return 0;
if (count == 1) return 1;
if (count < 10) return 2;
if (count < 100) return 3;
return 4;
}
public static int minLength(String s, int k) {
int n = s.length();
int[][] dp = new int[n + 1][k + 1];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
if (dp[i][j] == Integer.MAX_VALUE) continue;
int count = 0;
for (int l = i; l < n; l++) {
if (s.charAt(l) == s.charAt(i)) count++;
int needDelete = l - i + 1 - count;
if (j + needDelete <= k) {
dp[l + 1][j + needDelete] = Math.min(dp[l + 1][j + needDelete], dp[i][j] + compressLength(count));
}
}
}
}
return Arrays.stream(dp[n]).min().getAsInt();
}
public static void main(String[] args) {
String s = "aaabcccd";
int k = 2;
System.out.println(minLength(s, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
int compressLength(int c) {
if (c == 0) return 0;
if (c == 1) return 1;
if (c < 10) return 2;
if (c < 100) return 3;
return 4;
}
int minLength(string s, int k) {
int n = s.length();
vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
if (dp[i][j] == INT_MAX) continue;
int count = 0;
for (int l = i; l < n; ++l) {
if (s[l] == s[i]) count++;
int needDelete = l - i + 1 - count;
if (j + needDelete <= k) {
dp[l + 1][j + needDelete] = min(dp[l + 1][j + needDelete], dp[i][j] + compressLength(count));
}
}
}
}
int result = INT_MAX;
for (int j = 0; j <= k; ++j) result = min(result, dp[n][j]);
return result;
}
int main() {
string s = "aaabcccd";
int k = 2;
cout << minLength(s, k) << endl;
return 0;
}function compressLength(c) {
if (c === 0) return 0;
if (c === 1) return 1;
if (c < 10) return 2;
if (c < 100) return 3;
return 4;
}
function minLength(s, k) {
let n = s.length;
let dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(Infinity));
dp[0][0] = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j <= k; j++) {
if (dp[i][j] === Infinity) continue;
let count = 0;
for (let l = i; l < n; l++) {
if (s[l] === s[i]) count++;
let needDelete = l - i + 1 - count;
if (j + needDelete <= k) {
dp[l + 1][j + needDelete] = Math.min(dp[l + 1][j + needDelete], dp[i][j] + compressLength(count));
}
}
}
}
return Math.min(...dp[n]);
}
// Example usage
const s = "aaabcccd";
const k = 2;
console.log(minLength(s, k));#include <stdio.h>
#include <string.h>
#include <limits.h>
int compressLength(int c) {
if (c == 0) return 0;
if (c == 1) return 1;
if (c < 10) return 2;
if (c < 100) return 3;
return 4;
}
int minLength(char* s, int k) {
int n = strlen(s);
int dp[n+1][k+1];
for (int i = 0; i <= n; i++) for (int j = 0; j <= k; j++) dp[i][j] = INT_MAX;
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
if (dp[i][j] == INT_MAX) continue;
int cnt = 0;
for (int l = i; l < n; l++) {
if (s[l] == s[i]) cnt++;
int needed = l - i + 1 - cnt;
if (j + needed <= k) {
dp[l+1][j+needed] = fmin(dp[l+1][j+needed], dp[i][j] + compressLength(cnt));
}
}
}
}
int result = INT_MAX;
for (int j = 0; j <= k; j++) result = fmin(result, dp[n][j]);
return result;
}
int main() {
char s[] = "aaabcccd";
int k = 2;
int result = minLength(s, k);
printf("%d\n", result);
return 0;
}using System;
class Solution {
private static int CompressLength(int c) {
if (c == 0) return 0;
if (c == 1) return 1;
if (c < 10) return 2;
if (c < 100) return 3;
return 4;
}
public static int MinLength(string s, int k) {
int n = s.Length;
int[,] dp = new int[n + 1, k + 1];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= k; j++)
dp[i, j] = int.MaxValue;
dp[0, 0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
if (dp[i, j] == int.MaxValue) continue;
int count = 0;
for (int l = i; l < n; l++) {
if (s[l] == s[i]) count++;
int needDelete = l - i + 1 - count;
if (j + needDelete <= k) {
dp[l + 1, j + needDelete] = Math.Min(dp[l + 1, j + needDelete], dp[i, j] + CompressLength(count));
}
}
}
}
int result = int.MaxValue;
for (int j = 0; j <= k; j++)
result = Math.Min(result, dp[n, j]);
return result;
}
static void Main() {
string s = "aaabcccd";
int k = 2;
Console.WriteLine(MinLength(s, k));
}
}The Python solution breaks down the problem using a helper function to determine the compression length. It uses a list of lists to maintain the DP table and employs nested loops to fill it according to the defined rules.
Time Complexity: O(n^3). The algorithm checks multiple scenarios for compression and deletion decisions.
Space Complexity: O(n*k) for maintaining the DP states.
Approach 2: Approach 2: Greedy Algorithm with Counting
In this greedy approach, we identify segments of identical characters and evaluate them individually, considering their entire group in the adjustments. By counting the length of these segments, we can make informed decisions about deletions that do not depend on the widely traversed DP table, reducing some overhead complexity.
def min_length(s, k):
freq = [0] * 26
for c in s:
freq[ord(c) - ord('a')] += 1
freq.sort(reverse=True)
for i in range(26):
if k <= 0:
break
if freq[i] > 0:
delete_count = freq[i] - (1 if freq[i] == 1 else 0)
to_delete = min(delete_count, k)
freq[i] -= to_delete
k -= to_delete
length = 0
for f in freq:
if f > 0:
length += 1 if f == 1 else 1 + (2 if f < 10 else 3 if f < 100 else 4)
return length
if __name__ == '__main__':
s = "aaabcccd"
k = 2
print(min_length(s, k))import java.util.Arrays;
public class StringCompressionGreedy {
public static int minLength(String s, int k) {
int[] freq = new int[26];
for (char c : s.toCharArray()) freq[c - 'a']++;
Arrays.sort(freq);
for (int i = 25; i >= 0 && k > 0; i--) {
if (freq[i] > 0) {
int deleteCount = freq[i] - (freq[i] == 1 ? 0 : 1);
deleteCount = Math.min(deleteCount, k);
freq[i] -= deleteCount;
k -= deleteCount;
}
}
int length = 0;
for (int f : freq) {
if (f > 0) {
length += f == 1 ? 1 : 1 + (f < 10 ? 2 : f < 100 ? 3 : 4);
}
}
return length;
}
public static void main(String[] args) {
String s = "aaabcccd";
int k = 2;
System.out.println(minLength(s, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minLength(const string& s, int k) {
vector<int> freq(26, 0);
for (char c : s) freq[c - 'a']++;
sort(freq.rbegin(), freq.rend());
for (int i = 0; i < 26 && k > 0; i++) {
if (freq[i] > 0) {
int deleteCount = freq[i] - (freq[i] == 1 ? 0 : 1);
deleteCount = min(deleteCount, k);
freq[i] -= deleteCount;
k -= deleteCount;
}
}
int length = 0;
for (int f : freq) {
if (f > 0) {
length += f == 1 ? 1 : 1 + (f < 10 ? 2 : f < 100 ? 3 : 4);
}
}
return length;
}
int main() {
string s = "aaabcccd";
int k = 2;
cout << minLength(s, k) << endl;
return 0;
}function minLength(s, k) {
const freq = Array.from({length: 26}, () => 0);
for (const c of s) {
freq[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
freq.sort((a, b) => b - a);
for (let i = 0; i < 26 && k > 0; i++) {
if (freq[i] > 0) {
const deleteCount = freq[i] - (freq[i] === 1 ? 0 : 1);
const toDelete = Math.min(deleteCount, k);
freq[i] -= toDelete;
k -= toDelete;
}
}
let length = 0;
for (const f of freq) {
if (f > 0) {
length += f === 1 ? 1 : 1 + (f < 10 ? 2 : f < 100 ? 3 : 4);
}
}
return length;
}
// Example usage
const s = "aaabcccd";
const k = 2;
console.log(minLength(s, k));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int cmpint(const void *a, const void *b) {
return (*(int*)b - *(int*)a);
}
int minLength(char *s, int k) {
int n = strlen(s);
int freq[26] = {0}, maxFreq[26] = {0};
for (int i = 0; i < n; i++) freq[s[i] - 'a']++;
memcpy(maxFreq, freq, sizeof(freq));
qsort(freq, 26, sizeof(int), cmpint);
for (int i = 0; i < 26 && k > 0; i++) {
if (freq[i] > 0) {
int deleteCount = freq[i] - (freq[i] == 1 ? 0 : 1);
deleteCount = deleteCount < k ? deleteCount : k;
freq[i] -= deleteCount;
k -= deleteCount;
}
}
int length = 0;
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
length += freq[i] == 1 ? 1 : 1 + (freq[i] < 10 ? 2 : freq[i] < 100 ? 3 : 4);
}
}
return length;
}
int main() {
char s[] = "aaabcccd";
int k = 2;
printf("%d\n", minLength(s, k));
return 0;
}using System;
class Solution {
public static int MinLength(string s, int k) {
int[] freq = new int[26];
foreach (char c in s) {
freq[c - 'a']++;
}
Array.Sort(freq, (a, b) => b.CompareTo(a));
for (int i = 0; i < 26 && k > 0; i++) {
if (freq[i] > 0) {
int deleteCount = freq[i] - (freq[i] == 1 ? 0 : 1);
deleteCount = Math.Min(deleteCount, k);
freq[i] -= deleteCount;
k -= deleteCount;
}
}
int length = 0;
foreach (int f in freq) {
if (f > 0) {
length += f == 1 ? 1 : 1 + (f < 10 ? 2 : f < 100 ? 3 : 4);
}
}
return length;
}
static void Main() {
string s = "aaabcccd";
int k = 2;
Console.WriteLine(MinLength(s, k));
}
}The Python implementation uses an array to gather character frequencies and sorts it in descending order. The frequency list is then manipulated to use the allowed deletions optimally, simplifying subsequent compressed length calculations.
Time Complexity: O(n + m log m), where m = 26. Sorting the frequency counts is efficient enough given the small alphabet size.
Space Complexity: O(m) for the frequency list.
Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming with Subproblems | Time Complexity: O(n^3). The algorithm checks multiple scenarios for compression and deletion decisions. Space Complexity: O(n*k) for maintaining the DP states. |
| Approach 2: Greedy Algorithm with Counting | Time Complexity: O(n + m log m), where m = 26. Sorting the frequency counts is efficient enough given the small alphabet size. Space Complexity: O(m) for the frequency list. |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Subproblems | O(n^2 * k) | O(n * k) | General case and interview setting where optimal compression length is required |
| Greedy Algorithm with Counting | O(n^2) | O(1) | Quick heuristic reasoning about runs and deletions when exploring compression strategies |
Frequently asked questions
Is String Compression II easy or hard?
String Compression II is classified as a Hard problem because it combines run-length encoding logic with dynamic programming and deletion constraints. Correctly modeling the state transitions and compression length updates requires careful reasoning.
String Compression II Python/Java solution
Most implementations use top-down recursion with memoization or bottom-up DP. The logic tracks the current index, remaining deletions, and how run-length encoding length changes when counts cross thresholds like 1, 9, and 99. The same algorithm translates directly across Python, Java, C++, and other languages.
How to solve String Compression II in O(n)?
An exact O(n) solution is not known for the full problem because each position may consider multiple future grouping choices. The commonly accepted optimal solution uses dynamic programming with O(n^2 * k) time, which handles the interaction between deletions and run-length encoding boundaries.
What is the best approach for String Compression II?
Dynamic programming with memoized subproblems is the most reliable approach. The state typically tracks the current index and remaining deletions, while iterating forward to build compression groups. This guarantees the minimum encoded length and runs in O(n^2 * k) time with O(n * k) space.
Is String Compression II asked at Google/Amazon/Meta?
String compression and dynamic programming problems with deletion constraints frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. This problem tests state design, compression logic, and handling of digit-length transitions in run-length encoding.
What data structure is used in String Compression II?
The main structure is a dynamic programming table or memoization cache keyed by index and remaining deletions. During transitions, counters track character frequencies and run lengths while scanning the string.
What is the time complexity of String Compression II?
The optimal dynamic programming solution runs in O(n^2 * k) time because for each index and deletion count you may extend a run across the remaining string. Space complexity is O(n * k) for the DP table or memoization cache.