You are given a string s and an integer k. Your task is to delete at most k characters from s so that the length of the run-length encoded version of s is as short as possible.
The run-length encoding of a string compresses repeated consecutive characters into a single character followed by the count (if the count is more than 1). For example, aaabcccd is encoded as a3bc3d, which has length 6.
k characters anywhere in s.k deletions.Constraints:
1 <= s.length <= 1000 <= k <= s.lengths consists of lowercase English letters only.
At first glance, the problem seems to invite a brute-force approach: try all possible ways to delete up to k characters, compress each resulting string, and find the minimum length. However, with up to 100 characters and possibly 100 deletions, the number of combinations is enormous and not feasible to check individually.
To solve this efficiently, we need to avoid recalculating the same subproblems repeatedly. Since the result depends on the current position in the string, the number of deletions left, and the current run of characters, it is a classic candidate for dynamic programming (DP).
The key insight is to use memoization to cache results for subproblems defined by the current index in the string and the remaining number of deletions. This way, we avoid redundant calculations and ensure that our solution is efficient even for the largest allowed inputs.
We use a recursive dynamic programming approach with memoization. At each position in the string, we decide:
For each subproblem, we record:
i: The current position in the string.k: The number of deletions remaining.i with k deletions left.
k < 0, return infinity (invalid). If i >= len(s), return 0 (no characters left).
s[i] and solve the subproblem at i+1 with k-1 deletions left.
s[i] and extend the run as far as possible:
i, count how many deletions are needed to make all characters in the run the same as s[i].i, k) pair to avoid redundant work.
To compute the compressed length, remember:
Example Input: s = "aaabcccd", k = 2
At each step, the DP explores both deleting and keeping the current character, and for "keeping", it tries to extend the run by possibly deleting intervening characters, always choosing the minimum compressed length.
Brute-force approach: Would try all possible subsets of deletions (up to 2n), and for each, compress the string, which is infeasible for n up to 100.
Optimized DP approach:
O(n * k) subproblems, since i can range from 0 to n and k from 0 to k.
O(n) possible runs (from i up to n), but since n is small (≤100), this is acceptable.
O(n^2 * k)
O(n * k) for memoization.
This problem is a classic example of using dynamic programming to avoid redundant calculations in a problem with overlapping subproblems and optimal substructure. By carefully defining our state and memoizing results, we can efficiently explore all possible ways to delete up to k characters and minimize the compressed length. The solution elegantly balances recursion, memoization, and run-length encoding logic to handle all edge cases within the given constraints.
from functools import lru_cache
class Solution:
def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
n = len(s)
@lru_cache(maxsize=None)
def dp(i, k):
if k < 0:
return float('inf')
if i >= n or n - i <= k:
return 0
res = float('inf')
cnt = [0] * 26
most = 0
for j in range(i, n):
idx = ord(s[j]) - ord('a')
cnt[idx] += 1
most = max(most, cnt[idx])
del_needed = (j - i + 1) - most
if k - del_needed < 0:
continue
length = 1
if most > 1:
length += len(str(most))
res = min(res, length + dp(j + 1, k - del_needed))
return res
return dp(0, k)
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
class Solution {
public:
int dp[101][101];
int getLength(int cnt) {
if (cnt == 1) return 1;
if (cnt < 10) return 2;
if (cnt < 100) return 3;
return 4;
}
int helper(const string& s, int i, int k) {
int n = s.size();
if (k < 0) return 1e9;
if (i >= n || n - i <= k) return 0;
if (dp[i][k] != -1) return dp[i][k];
int res = 1e9;
int cnt[26] = {0};
int most = 0;
for (int j = i; j < n; ++j) {
cnt[s[j] - 'a']++;
most = max(most, cnt[s[j] - 'a']);
int del_needed = (j - i + 1) - most;
if (k - del_needed < 0) continue;
res = min(res, getLength(most) + helper(s, j + 1, k - del_needed));
}
return dp[i][k] = res;
}
int getLengthOfOptimalCompression(string s, int k) {
memset(dp, -1, sizeof(dp));
return helper(s, 0, k);
}
};
import java.util.Arrays;
class Solution {
private int[][] dp;
private int getLength(int cnt) {
if (cnt == 1) return 1;
if (cnt < 10) return 2;
if (cnt < 100) return 3;
return 4;
}
private int helper(String s, int i, int k) {
int n = s.length();
if (k < 0) return 100000;
if (i >= n || n - i <= k) return 0;
if (dp[i][k] != -1) return dp[i][k];
int[] cnt = new int[26];
int most = 0, res = 100000;
for (int j = i; j < n; ++j) {
cnt[s.charAt(j) - 'a']++;
most = Math.max(most, cnt[s.charAt(j) - 'a']);
int del_needed = (j - i + 1) - most;
if (k - del_needed < 0) continue;
res = Math.min(res, getLength(most) + helper(s, j + 1, k - del_needed));
}
dp[i][k] = res;
return res;
}
public int getLengthOfOptimalCompression(String s, int k) {
dp = new int[s.length() + 1][k + 2];
for (int[] row : dp) Arrays.fill(row, -1);
return helper(s, 0, k);
}
}
var getLengthOfOptimalCompression = function(s, k) {
const n = s.length;
const memo = new Map();
function getLen(cnt) {
if (cnt === 1) return 1;
if (cnt < 10) return 2;
if (cnt < 100) return 3;
return 4;
}
function dp(i, k) {
if (k < 0) return Infinity;
if (i >= n || n - i <= k) return 0;
const key = i + ',' + k;
if (memo.has(key)) return memo.get(key);
let res = Infinity;
const cnt = Array(26).fill(0);
let most = 0;
for (let j = i; j < n; ++j) {
cnt[s.charCodeAt(j) - 97]++;
most = Math.max(most, cnt[s.charCodeAt(j) - 97]);
const del_needed = (j - i + 1) - most;
if (k - del_needed < 0) continue;
res = Math.min(res, getLen(most) + dp(j + 1, k - del_needed));
}
memo.set(key, res);
return res;
}
return dp(0, k);
};