1531. String Compression II

using System;
using System.Collections.Generic;
public class Solution {
    private Dictionary<int, int> memo = new Dictionary<int, int>();
    private HashSet<int> add = new HashSet<int> { 1, 9, 99 };
    public int GetLengthOfOptimalCompression(string s, int k) {
        return Dp(s, 0, (char)('a' + 26), 0, k);
    }
    private int Dp(string s, int idx, char lastChar, int lastCharCount, int k) {
        if (k < 0) {
            return int.MaxValue / 2;
        }
        if (idx == s.Length) {
            return 0;
        }
        int key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k;
        if (memo.ContainsKey(key)) {
            return memo[key];
        }
        int deleteChar = Dp(s, idx + 1, lastChar, lastCharCount, k - 1);
        int keepChar;
        if (s[idx] == lastChar) {
            keepChar = Dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (add.Contains(lastCharCount) ? 1 : 0);
        } else {
            keepChar = Dp(s, idx + 1, s[idx], 1, k) + 1;
        }
        int res = Math.Min(keepChar, deleteChar);
        memo[key] = res;
        return res;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private unordered_map<int, int> memo = new unordered_map<int, int>();
    private HashSet<int> add = new HashSet<int> { 1, 9, 99 };
    public int GetLengthOfOptimalCompression(string s, int k) {
        return Dp(s, 0, (char)('a' + 26), 0, k);
    }
    private int Dp(string s, int idx, char lastChar, int lastCharCount, int k) {
        if (k < 0) {
            return int.MaxValue / 2;
        }
        if (idx == s.size()) {
            return 0;
        }
        int key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k;
        if (memo.count(key)) {
            return memo[key];
        }
        int deleteChar = Dp(s, idx + 1, lastChar, lastCharCount, k - 1);
        int keepChar;
        if (s[idx] == lastChar) {
            keepChar = Dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (add.Contains(lastCharCount) ? 1 : 0);
        } else {
            keepChar = Dp(s, idx + 1, s[idx], 1, k) + 1;
        }
        int res = min(keepChar, deleteChar);
        memo[key] = res;
        return res;
    }
}

import java.util.*;

public class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();
    private Set<Integer> add = Set.of(1, 9, 99);

    public int getLengthOfOptimalCompression(String s, int k) {
        return dp(s, 0, (char) ('a' + 26), 0, k);
    }

    private int dp(String s, int idx, char lastChar, int lastCharCount, int k) {
        if (k < 0) {
            return Integer.MAX_VALUE / 2;
        }

        if (idx == s.length()) {
            return 0;
        }

        int key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k;

        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int deleteChar = dp(s, idx + 1, lastChar, lastCharCount, k - 1);
        int keepChar;
        if (s.charAt(idx) == lastChar) {
            keepChar = dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (add.contains(lastCharCount) ? 1 : 0);
        } else {
            keepChar = dp(s, idx + 1, s.charAt(idx), 1, k) + 1;
        }
        int res = Math.min(keepChar, deleteChar);
        memo.put(key, res);

        return res;
    }
}

class Solution {
    constructor() {
        this.memo = new Map();
        this.add = new Set([1, 9, 99]);
    }

    getLengthOfOptimalCompression(s, k) {
        return this.dp(s, 0, String.fromCharCode('a'.charCodeAt(0) + 26), 0, k);
    }

    dp(s, idx, lastChar, lastCharCount, k) {
        if (k < 0) {
            return Number.MAX_SAFE_INTEGER / 2;
        }

        if (idx === s.length) {
            return 0;
        }

        const key = idx * 101 * 27 * 101 + (lastChar.charCodeAt(0) - 'a'.charCodeAt(0)) * 101 * 101 + lastCharCount * 101 + k;

        if (this.memo.has(key)) {
            return this.memo.get(key);
        }

        const deleteChar = this.dp(s, idx + 1, lastChar, lastCharCount, k - 1);
        let keepChar;
        if (s[idx] === lastChar) {
            keepChar = this.dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (this.add.has(lastCharCount) ? 1 : 0);
        } else {
            keepChar = this.dp(s, idx + 1, s[idx], 1, k) + 1;
        }

        const res = Math.min(keepChar, deleteChar);
        this.memo.set(key, res);

        return res;
    }
}

class Solution:
    def __init__(self):
        self.memo = {}
        self.add = {1, 9, 99}

    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        return self.dp(s, 0, chr(ord('a') + 26), 0, k)

    def dp(self, s: str, idx: int, last_char: str, last_char_count: int, k: int) -> int:
        if k < 0:
            return float('inf') / 2

        if idx == len(s):
            return 0

        key = idx * 101 * 27 * 101 + (ord(last_char) - ord('a')) * 101 * 101 + last_char_count * 101 + k

        if key in self.memo:
            return self.memo[key]

        delete_char = self.dp(s, idx + 1, last_char, last_char_count, k - 1)
        if s[idx] == last_char:
            keep_char = self.dp(s, idx + 1, last_char, last_char_count + 1, k) + (1 if last_char_count in self.add else 0)
        else:
            keep_char = self.dp(s, idx + 1, s[idx], 1, k) + 1

        res = min(keep_char, delete_char)
        self.memo[key] = res

        return res

package main

import "math"

type Solution struct {
    memo map[int]int
    add  map[int]struct{}
}

func Constructor() Solution {
    return Solution{memo: make(map[int]int), add: map[int]struct{}{1: {}, 9: {}, 99: {}}}
}

func (this *Solution) GetLengthOfOptimalCompression(s string, k int) int {
    return this.dp(s, 0, byte('a'+26), 0, k)
}

func (this *Solution) dp(s string, idx int, lastChar byte, lastCharCount int, k int) int {
    if k < 0 {
        return math.MaxInt32 / 2
    }

    if idx == len(s) {
        return 0
    }

    key := idx*101*27*101 + int(lastChar-'a')*101*101 + lastCharCount*101 + k

    if res, found := this.memo[key]; found {
        return res
    }

    deleteChar := this.dp(s, idx+1, lastChar, lastCharCount, k-1)
    var keepChar int
    if s[idx] == lastChar {
        keepChar = this.dp(s, idx+1, lastChar, lastCharCount+1, k)
        if _, found := this.add[lastCharCount]; found {
            keepChar++
        }
    } else {
        keepChar = this.dp(s, idx+1, s[idx], 1, k) + 1
    }

    res := min(deleteChar, keepChar)
    this.memo[key] = res

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Algorithm

Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (chaîne, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.

Для определения состояния DP используем следующие параметры: количество пройденных символов (чтобы знать, какой символ обрабатывать следующим), последний добавленный символ в сжатую строку (чтобы определить изменение сжатия при добавлении нового символа), количество последнего символа (для правильного изменения длины сжатия при добавлении символа) и количество оставшихся символов, которые можно удалить.

Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎