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.lengths contains only lowercase English letters.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.
The solution defines a helper function compressLength which calculates the length of the compressed representation given a count. The main function minLength initializes a DP array and iteratively fills it by considering each character, counting contiguous appearances, and updating the DP state to find the minimum compression lengths achievable with allowed deletions.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3). For each starting point, we may need to process every subsequent character and make decisions up to k deletions.
Space Complexity: O(n*k). Space used by the DP table.
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.
This C solution uses a frequency table to count occurrences of each character and adjusts the counts after sorting them. By decreasing the most frequent occurrences, we fit within the limit of deletions. The resulting array gives us a simple method to calculate the resulting minimal compressed length.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m log m) where n is the length of the string and m = 26 (constant time, simplified in this case).
Space Complexity: O(m) for frequency arrays.
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming with Subproblems | Time Complexity: O(n^3). For each starting point, we may need to process every subsequent character and make decisions up to k deletions. Space Complexity: O(n*k). Space used by the DP table. |
| Approach 2: Greedy Algorithm with Counting | Time Complexity: O(n + m log m) where n is the length of the string and m = 26 (constant time, simplified in this case). Space Complexity: O(m) for frequency arrays. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,632 views views
Watch 9 more video solutions →Practice String Compression II with our built-in code editor and test cases.
Practice on FleetCode