1531. String Compression II

String Compression II

Problem Description

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.

Approach) Dynamic Programming (DP)

Let dp[i][j] be the answer to the sub-problem with s[0..(i-1)] and j deletions.

For dp[i][j], we have two options:

1. delete s[i - 1]. Then the result is dp[i - 1][j - 1].
2. keep s[i - 1]. Then we can try to construct the optimal solution by scanning backward and delete those letters are different from s[i - 1]. Those letters that are same as s[i - 1] will be merged using run-length encoding
   1. We scan t from i to 1.
   2. If s[t - 1] == s[i - 1] then we merge them together; otherwise we delete s[t - 1]. We store the merge count using cnt and the deleted count using del.
   3. We can update dp[i][j] using dp[t - 1][j - del] and 1 + (cnt >= 100 ? 3 : cnt >= 10 ? 2 : cnt >= 2 ? 1 : 0)) which is the number of characters required to encode the merged s[i - 1] section.

Code:

const getLengthOfOptimalCompression = function (s, k) {
  const n = s.length
  const dp = new Array(n + 1).fill(n).map((row) => new Array(k + 1).fill(n))
  dp[0][0] = 0

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= k; j++) {
      let letterCount = 0
      let deletion = 0
      // keep s[i], compress same letters, remove different letters
      for (let l = i; l >= 1; l--) {
        if (s.charAt(l - 1) === s.charAt(i - 1)) letterCount++
        else deletion++
        // places = length needed to rep compressed letters.
        // 0 places for count = 1,0, 1 place = <10, 10-99 requires 2 places, 100+ requires 3
        let places = 0
        if (letterCount >= 100) places = 3
        else if (letterCount >= 10) places = 2
        else if (letterCount >= 2) places = 1
        if (j - deletion >= 0) {
          dp[i][j] = Math.min(dp[i][j], dp[l - 1][j - deletion] + 1 + places)
        }
      }
      // delete
      if (j > 0) {
        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1])
      }
    }
  }
  return dp[n][k]
}

Another)

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
const getLengthOfOptimalCompression = function(s, k) {
  const m = new Map()
  function counter(start, last, lastCount, left) {
    if(left < 0) return Infinity
    if(start >= s.length) return 0
    let res
    const k = `${start}-${last}-${lastCount}-${left}`
    if(m.has(k)) return m.get(k)
    if(s[start] === last) {
      const incr = (lastCount === 1 || lastCount === 9 || lastCount === 99) ? 1 : 0
      res = incr + counter(start + 1, last, lastCount + 1, left)
    } else {
      const keepCounter = 1 + counter(start + 1, s[start], 1, left)
      const delCounter = counter(start + 1, last,  lastCount, left - 1)
      res = Math.min(keepCounter, delCounter)
    }
    m.set(k, res)
    return res
  }
  return counter(0, '', 0, k)
};

Another)

var getLengthOfOptimalCompression = function(s, remove) {
    const memo = new Map();    
    const state_key = (start,count) => [start, count].toString();
    const range = (start,length) => [...Array(length - start).keys()].map(i => i + start);
    const length = freq => freq > 1  ? freq.toString().length : 0;
    const compressed = freq => 1 + length(freq);
    const removed = (start, end, dups) => (end - start + 1) - dups;
    const dp = (start, remove) => {
        const cur_length = s.length - start;
        if(cur_length === 0 || remove >= cur_length) return 0;
        const key = state_key(start, remove);
        if(memo.has(key)) return memo.get(key);
        const interval_freqs = new Map();
        let [res, max_freq] = [Infinity, 0];
        for(let compressed_end of range(start, s.length)) {
            const char = s[compressed_end];
            interval_freqs.set(char, (interval_freqs.get(char) || 0) + 1);
            max_freq = Math.max(max_freq, interval_freqs.get(char));
            let next_remove = remove - removed(start, compressed_end,max_freq);
            if(next_remove >= 0)
                res = Math.min(res, compressed(max_freq) + dp(compressed_end + 1, next_remove));
        }
        memo.set(key, res);
        return res;
    };
    return dp(0, remove);
}

Another) Memo with backtrack 

var getLengthOfOptimalCompression = function(s, k) {
    const memo = new Map()
    
    const backtrack = (i, lastChar, lastCharCount, k) => {
        if (k < 0) return Number.POSITIVE_INFINITY
        if (i >= s.length) return 0
        
        const memoKey = `${i}#${lastChar}#${lastCharCount}#${k}`
        if (memoKey in memo) return memo[memoKey]
        
        if (s[i] === lastChar) {
            const incrementor = [1, 9, 99].includes(lastCharCount) ? 1 : 0
            memo[memoKey] = incrementor + backtrack(i+1, lastChar, lastCharCount+1, k)
        } else {
            memo[memoKey] = Math.min(
                1 + backtrack(i+1, s[i], 1, k), //keep char
                backtrack(i+1, lastChar, lastCharCount, k-1) //delete char
            )
        }
        return memo[memoKey]
    }
    return backtrack(0, '', 0, k)
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1531. String Compression II

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!