> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/string-compression-ii.md). # String Compression II [Run-length encoding](http://en.wikipedia.org/wiki/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. ```java class Solution { Integer[][][] memo; public int getLengthOfOptimalCompression(String s, int k) { List count = new ArrayList<>(); char prevChar = ' '; int cnt = 0; // build a list of consecutive chars count, aaabbcc -> {{a, 3}, {b, 2}, {c, 2}} for (char c : s.toCharArray()) { if (prevChar != c) { if (cnt != 0) count.add(new int[]{prevChar - 'a', cnt}); cnt = 1; prevChar = c; } else cnt++; } count.add(new int[]{prevChar - 'a', cnt}); memo = new Integer[count.size() + 1][k + 1][s.length() + 1]; return helper(count, 0, 0, k); } // 'extraChars' is a number of additional consecutive chars to be added, for cases like `aabbaa` and we delete two `b` // 'index' is the counter, we go through all `count` list elements until we reach the end // 'toDelete' is the remaining chars we can delete public int helper(List count, int extraChars, int index, int toDelete) { // Reached the end of count array if (index == count.size()) return 0; if (memo[index][toDelete][extraChars] != null) return memo[index][toDelete][extraChars]; int[] curr = count.get(index); int countOfChar = curr[1] + extraChars; // first just try to keep everything int ans = lengthCounter(countOfChar) + helper(count, 0, index + 1, toDelete); // We are interested in main-changes only, // like a10 -> a9, a2 -> a1, a1 -> a0(Nothing ->'') // where string gets shorter for (int desired : new int[]{0, 1, 9}) { int toRemove = countOfChar - desired; // how many chars to be removed to achieve "desired" if (toRemove <= toDelete && desired < countOfChar) ans = Math.min(ans, helper(count, 0, index + 1, toDelete - toRemove) + lengthCounter(desired)); } // now let's handle the case like `aabbaa` -> `aaaa` // what we do is go through all the next consecutive chars and try to remove them entirely // in case we encounter the same character as we have now, we just pass the current count as `a` parameter // e.g. `aaabbaa` -> `{{a,3},{b,2},{a,2}} // we remove {b,2} and call f(count, 3, j, res), // where res will be (k-charsWeRemovedInBetween) // and 3 is the count of `a` on the beginning which is passed to sum up with the two `a` we have in the end // which results in (2+3)=5 consecutive `a` chars, what we have when we remove both `b` int copyOfDelete = toDelete; for (int j = index + 1; j < count.size() && copyOfDelete >= 0; j++) { int[] next = count.get(j); // If we find a matching set of char, ex: 'aabbaa' -> 'a2b2a2' // so if we can delete 2*b, then we need to join a2a2 -> a4 if (next[0] == curr[0]) { ans = Math.min(ans, helper(count, countOfChar, j, copyOfDelete)); break; } // Assuming we will delete all the chars in between copyOfDelete -= next[1]; } memo[index][toDelete][extraChars] = ans; return ans; } // length of char + its count, where n is a count of that char // if n == 15, l(15) = 3 -> e.g. `a15` public int lengthCounter(int n) { if (n <= 1) return n; if (n < 10) return 2; if (n < 100) return 3; return 4; } } ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/string-compression-ii.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.