1531. String Compression II LeetCode Solution
In this guide, you will get 1531. String Compression II LeetCode Solution with the best time and space complexity. The solution to String Compression II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- String Compression II solution in C++
- String Compression II solution in Java
- String Compression II solution in Python
- Additional Resources
Problem Statement of String Compression II
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 <= 100
0 <= k <= s.length
s contains only lowercase English letters.
Complexity Analysis
- Time Complexity: O(n^2k)
- Space Complexity: O(nk)
1531. String Compression II LeetCode Solution in C++
class Solution {
public:
int getLengthOfOptimalCompression(string s, int k) {
vector<vector<int>> mem(s.length(), vector<int>(k + 1, kMax));
return compression(s, 0, k, mem);
}
private:
static constexpr int kMax = 101;
// Returns the length of the optimal compression of s[i..n) with at most k
// deletion.
int compression(const string& s, int i, int k, vector<vector<int>>& mem) {
if (k < 0)
return kMax;
if (i == s.length() || s.length() - i <= k)
return 0;
if (mem[i][k] != kMax)
return mem[i][k];
int maxFreq = 0; // the maximum frequency in s[i..j]
vector<int> count(128);
// Make letters in s[i..j] be the same.
// Keep the letter that has the maximum frequency in this range and remove
// the other letters.
for (int j = i; j < s.length(); ++j) {
maxFreq = max(maxFreq, ++count[s[j]]);
mem[i][k] = min( //
mem[i][k], //
getLength(maxFreq) +
compression(s, j + 1, k - (j - i + 1 - maxFreq), mem));
}
return mem[i][k];
}
// Returns the length to compress `maxFreq`.
int getLength(int maxFreq) {
if (maxFreq == 1)
return 1; // c
if (maxFreq < 10)
return 2; // [1-9]c
if (maxFreq < 100)
return 3; // [1-9][0-9]c
return 4; // [1-9][0-9][0-9]c
}
};
/* code provided by PROGIEZ */1531. String Compression II LeetCode Solution in Java
class Solution {
public int getLengthOfOptimalCompression(String s, int k) {
int[][] mem = new int[s.length()][k + 1];
Arrays.stream(mem).forEach(A -> Arrays.fill(A, kMax));
return compression(s, 0, k, mem);
}
private static final int kMax = 101;
// Returns the length of the optimal compression of s[i..n) with at most k
// deletion.
private int compression(final String s, int i, int k, int[][] mem) {
if (k < 0)
return kMax;
if (i == s.length() || s.length() - i <= k)
return 0;
if (mem[i][k] != kMax)
return mem[i][k];
int maxFreq = 0;
int[] count = new int[128];
// Make letters in s[i..j] be the same.
// Keep the letter that has the maximum frequency in this range and remove
// the other letters.
for (int j = i; j < s.length(); ++j) {
maxFreq = Math.max(maxFreq, ++count[s.charAt(j)]);
mem[i][k] = Math.min( //
mem[i][k], //
getLength(maxFreq) + compression(s, j + 1, k - (j - i + 1 - maxFreq), mem));
}
return mem[i][k];
}
// Returns the length to compress `maxFreq`.
private int getLength(int maxFreq) {
if (maxFreq == 1)
return 1; // c
if (maxFreq < 10)
return 2; // [1-9]c
if (maxFreq < 100)
return 3; // [1-9][0-9]c
return 4; // [1-9][0-9][0-9]c
}
}
// code provided by PROGIEZ1531. String Compression II LeetCode Solution in Python
class Solution:
def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
def getLength(maxFreq: int) -> int:
"""Returns the length to compress `maxFreq`."""
if maxFreq == 1:
return 1 # c
if maxFreq < 10:
return 2 # [1-9]c
if maxFreq < 100:
return 3 # [1-9][0-9]c
return 4 # [1-9][0-9][0-9]c
@functools.lru_cache(None)
def dp(i: int, k: int) -> int:
"""Returns the length of optimal dp of s[i..n) with at most k deletion."""
if k < 0:
return math.inf
if i == len(s) or len(s) - i <= k:
return 0
ans = math.inf
maxFreq = 0 # the maximum frequency in s[i..j]
count = collections.Counter()
# Make letters in s[i..j] be the same.
# Keep the letter that has the maximum frequency in this range and remove
# the other letters.
for j in range(i, len(s)):
count[s[j]] += 1
maxFreq = max(maxFreq, count[s[j]])
ans = min(ans, getLength(maxFreq) +
dp(j + 1, k - (j - i + 1 - maxFreq)))
return ans
return dp(0, k)
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.