Skip to content

1531. String Compression II 👍

  • Time: $O(n^2k)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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)