String Compression Ii - Leetcode Solution

Problem statement: Given a string s and an integer k, you need to compress the string such that its length after compression is less than or equal to k. To compress the string, you can replace consecutive repeating characters with their count followed by the character. For example, aaabbbc can be compressed to 3a3bc, where 3a means "aaa" and 3bc means "bbbc". If the compressed string is longer than the original string, return the original string.

Example 1: Input: s = "aaabcccddeee", k = 7 Output: "a3bcccdeee" Explanation: The compressed string is "a3bcccdeee". The length of the compressed string is 10, which is less than the given k of 7. Therefore, the compressed string is returned.

Example 2: Input: s = "aaabcccddeee", k = 5 Output: "aaabcccddeee" Explanation: The compressed string is "a3bcccdeee". The length of the compressed string is 10, which is greater than the given k of 5. Therefore, the original string is returned.

Solution:

We can solve this problem using dynamic programming. We can define dp[i][j] as the minimum length of compressing the substring from index i to index j.

Case 1: If we don't compress the character at index i, then the length of the compressed string will be the length of the character at index i plus dp[i+1][j].

Case 2: If we compress the character at index i, then the length of the compressed string will be the length of the compressed substring plus the length of the remaining string. We need to consider all possible lengths of compressed substring at index i. Let's say we compress the substring of length l at index i, then the length of the compressed substring will be l + ceil(log10(count)) where count is the number of consecutive repeating characters. The length of the remaining string will be dp[i+l][j].

Therefore, dp[i][j] = min(1 + dp[i+1][j], length of compressed substring + dp[i+l][j]) where l can vary from 1 to j-i+1.

At the end, we need to return dp[0][n-1] where n is the length of the string.

Time Complexity: O(n^3 * log(k)) where n is the length of the string.

Here's the Python code for the same:

class Solution: def getLengthOfOptimalCompression(self, s: str, k: int) -> int: n = len(s) dp = [[float('inf')] * n for _ in range(n)] for i in range(n): dp[i][i] = 1 # to compress a single character for i in range(n-1): dp[i][i+1] = 1 if s[i] != s[i+1] else 2 # to compress two characters if they are different for l in range(3, n+1): # to compress multiple characters if they are different for i in range(n-l+1): j = i + l - 1 for m in range(i, j): dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j]) if self.getCount(s[i:j+1]) + k >= l: dp[i][j] = min(dp[i][j], 1 + dp[i+1][j]) # to not compress the character at index i for p in range(1, l): if l % p == 0: compressed_str = self.getCompressedStr(s[i:j+1], p) if len(compressed_str) + self.getCount(s[i:j+1]) + k - l >= 0: dp[i][j] = min(dp[i][j], len(compressed_str) + dp[i+p][j]) # to compress the character at index i return dp[0][n-1]

def getCount(self, s: str) -> int:
    count, res = 0, 0
    for i in range(len(s)):
        count += 1
        if i == len(s) - 1 or s[i] != s[i+1]:
            res += max(0, count - 1 - int(count == 1))
            count = 0
    return res

def getCompressedStr(self, s: str, k: int) -> str:
    res = ''
    for i in range(0, len(s), k):
        count = self.getCount(s[i:i+k])
        res += str(count) + s[i] if count > 1 else s[i]
    return res

1