String Compression II - Practice Coding Problems

String Compression II - 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.

Input & Output

Example 1 — Basic Compression

$ Input: s = "aaabcccd", k = 2

› Output: 4

💡 Note: Delete 'b' and one 'c' to get "aaaccd" which compresses to "a3c2d" (length 4)

Example 2 — Single Character Run

$ Input: s = "aabbaa", k = 2

› Output: 2

💡 Note: Delete the two 'b's to get "aaaa" which compresses to "a4" (length 2)

Example 3 — No Compression Benefit

$ Input: s = "ababacb", k = 0

› Output: 7

💡 Note: No deletions allowed, each character is single so compressed length equals original length

Constraints

1 ≤ s.length ≤ 100
0 ≤ k ≤ s.length
s contains only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Original string with scattered identical characters

Strategic Deletion

Remove characters to create longer runs of same characters

Compression

Apply run-length encoding to get minimum length

Key Takeaway

🎯 Key Insight: Strategic deletion of characters can create longer consecutive runs, leading to better compression ratios than the original string.

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that we can strategically delete characters to create longer runs of identical characters, reducing compression length. The optimal approach uses dynamic programming with memoization to explore all deletion possibilities efficiently. Time: O(n×k×26×n), Space: O(n×k×26×n)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n * k * 26 * n)	O(n * k * 26 * n)	Use recursion with memoization to avoid recomputing the same subproblems
Bottom-up Dynamic Programming	O(n² * k)	O(n * k)	Build solution iteratively using a 2D DP table to track optimal compression lengths
Brute Force (Generate All Subsequences)	O(2^n)	O(n)	Generate all possible subsequences by deleting at most k characters and find minimum compression length

Dynamic Programming with Memoization — Algorithm Steps

Define state: position, deletions used, current character, run length
Use memoization to cache computed states
For each position, try keeping or deleting the character

Visualization

Tap to expand

Step-by-Step Walkthrough

State Definition

Track position, remaining deletions, current character, and run count

Memoization

Cache results for each unique state to avoid recomputation

Optimal Path

Find minimum cost path through the decision tree

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_MEMO 100000

typedef struct {
    int i, kLeft, lastCount;
    char lastChar;
    int result;
} MemoEntry;

MemoEntry memo[MAX_MEMO];
int memoSize = 0;

int getLength(int count) {
    if (count == 1) return 1;
    if (count < 10) return 2;
    if (count < 100) return 3;
    return 4;
}

int findMemo(int i, int kLeft, char lastChar, int lastCount) {
    for (int j = 0; j < memoSize; j++) {
        if (memo[j].i == i && memo[j].kLeft == kLeft && 
            memo[j].lastChar == lastChar && memo[j].lastCount == lastCount) {
            return memo[j].result;
        }
    }
    return -1;
}

void addMemo(int i, int kLeft, char lastChar, int lastCount, int result) {
    if (memoSize < MAX_MEMO) {
        memo[memoSize].i = i;
        memo[memoSize].kLeft = kLeft;
        memo[memoSize].lastChar = lastChar;
        memo[memoSize].lastCount = lastCount;
        memo[memoSize].result = result;
        memoSize++;
    }
}

int dp(char* s, int i, int kLeft, char lastChar, int lastCount) {
    if (kLeft < 0) return 1000000;
    if (i == strlen(s)) {
        return lastCount > 0 ? getLength(lastCount) : 0;
    }
    
    int cached = findMemo(i, kLeft, lastChar, lastCount);
    if (cached != -1) return cached;
    
    int res = 1000000;
    
    // Delete current character
    int deleteRes = dp(s, i + 1, kLeft - 1, lastChar, lastCount);
    if (deleteRes < res) res = deleteRes;
    
    // Keep current character
    if (s[i] == lastChar) {
        int keepRes = dp(s, i + 1, kLeft, lastChar, lastCount + 1);
        if (keepRes < res) res = keepRes;
    } else {
        int prevLength = lastCount > 0 ? getLength(lastCount) : 0;
        int keepRes = prevLength + dp(s, i + 1, kLeft, s[i], 1);
        if (keepRes < res) res = keepRes;
    }
    
    addMemo(i, kLeft, lastChar, lastCount, res);
    return res;
}

int solution(char* s, int k) {
    memoSize = 0;
    return dp(s, 0, k, '\0', 0);
}

int main() {
    char s[101];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * k * 26 * n)

n positions × k deletions × 26 characters × max run length n

✓ Linear Growth

Space Complexity

O(n * k * 26 * n)

Memoization table stores states plus recursion stack

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler