String Compression II

public class Solution {
    private Map<Integer, Integer> cache = new HashMap<>();
    private Set<Integer> addCount = Set.of(1, 9, 99);
    
    public int optimalCompressionLength(String text, int k) {
        return calcDP(text, 0, (char) ('a' + 26), 0, k);
    }
    
    private int calcDP(String text, int index, char previousChar, int previousCount, int k) {
        if (k < 0) {
            return Integer.MAX_VALUE / 2;
        }
    
        if (index == text.length()) {
            return 0;
        }
    
        int cacheKey = index * 101 * 27 * 101 + (previousChar - 'a') * 101 * 101 + previousCount * 101 + k;
    
        if (cache.containsKey(cacheKey)) {
            return cache.get(cacheKey);
        }
    
        int keepCharacter;
        int eliminateCharacter = calcDP(text, index + 1, previousChar, previousCount, k - 1);
        if (text.charAt(index) == previousChar) {
            keepCharacter = calcDP(text, index + 1, previousChar, previousCount + 1, k) + (addCount.contains(previousCount) ? 1 : 0);
        } else {
            keepCharacter = calcDP(text, index + 1, text.charAt(index), 1, k) + 1;
        }
        int result = Math.min(keepCharacter, eliminateCharacter);
        cache.put(cacheKey, result);
    
        return result;
    }
}

The Java solution for the "String Compression II" problem uses dynamic programming with memoization to optimize the process of string compression under a given limit of character deletions ( k ). The main objective is to minimize the length of the compressed version of the string by strategically eliminating up to ( k ) characters.

The approach involves the following elements:

• Memoization is implemented using a HashMap called cache to store results of subproblems and avoid redundant calculations. This significantly reduces the execution time by remembering the results of previously computed scenarios.

• Recursive Function (calcDP): This function computes the optimal compressed length of a substring starting from a given index, with constraints defined by the previous character, its count in the current compression block, and the remaining deletions allowed ( k ).

• Parameters of calcDP:

  • text: The input text to be compressed.
  • index: The current position in the string.
  • previousChar: The character of the current compression block.
  • previousCount: The count of this character in the current block.
  • k: The remaining deletions allowed.

• Decision Points within calcDP:

  • If the current character is the same as previousChar, either keep it and potentially increase the count or discard it to use one of the allowed deletions.
  • If it’s different, start a new compression block or decide to remove the character.

• Performance Optimizations:

  • Compression Length Calculation: Adjusts the added length depending on certain thresholds (1, 9, 99), which reflects how integer lengths change in string formation (e.g., going from "9" to "10" increases the digit count).
  • Cache Key Creation: A unique key for the cache is constructed using a combination of current index, previous character, count, and remaining deletions. This ensures that identical scenarios across function calls do not require re-computation.

• Base and Edge Cases:

  • If ( k ) becomes negative, the function returns a very large number, indicating an invalid scenario.
  • At the end of the string (when ( index ) equals the length of text), it returns 0 as no more characters are left to process.

This method efficiently calculates the minimum compressed length considering deletions, utilizing both character continuation and strategic eliminations guided by recursive traversal of string choices and memoization of intermediate results.

class Solution:
    def minimizeLength(self, string: str, deletions: int) -> int:
        @lru_cache(None)
        def compress(index, curr_char, curr_count, deletions_left):
            if deletions_left < 0:
                return float('inf')
            if index == length:
                return 0
    
            remove_this_char = compress(index + 1, curr_char, curr_count, deletions_left - 1)
            if string[index] == curr_char:
                keep_this_char = compress(index + 1, curr_char, curr_count + 1, deletions_left) + (curr_count in [1, 9, 99])
            else:
                keep_this_char = compress(index + 1, string[index], 1, deletions_left) + 1
    
            return min(keep_this_char, remove_this_char)
    
        length = len(string)
        return compress(0, "", 0, deletions)

The given Python solution addresses the problem of compressing a string to a minimal length by potentially deleting up to a specified number of characters. The solution employs dynamic programming with memoization (lru_cache) for efficiency.

Here's an explanation on how the function minimizeLength works:

• Memoization Setup: The function compress is decorated with lru_cache(None) to cache the results of computations and speed up the process by avoiding redundant calculations.

• Base Conditions:

  • If deletions_left is less than zero, it indicates that more characters have been removed than allowed, so this path in the recursion returns a very high value (infinity).
  • If index reaches the end of the string (length), the recursion terminates as there are no more characters to process, returning 0.

• Recursive Decisions:

  • Removing Current Character: It recursively considers skipping the current character by reducing deletions_left and moving to the next index.
  • Keeping Current Character: If the current character matches curr_char, it increments curr_count and moves to the next character without changing the allowed deletions count. If it’s a new character, it resets curr_char and sets curr_count to 1, also adding to the length if this character initates a new count group (1, 9, 99 corresponding to length increases from additional digits).

• Choosing the Optimal Path: It returns the minimum of either keeping or removing the current character, thus ensuring the minimal length is achieved.

• Computation: Starts the compression from the first character with no deletions occurred and no characters initially counted.

This approach ensures that the function efficiently finds the minimal length of the string after allowed deletions while considering different scenarios to compress contiguous characters efficiently. The use of a dynamic programming strategy makes the solution suitable for longer strings and higher numbers of deletions, leveraging caching to reduce time complexity markedly.