Задача: 1531. String Compression II
Сложность: hard

Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной.

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

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.

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>

class Solution {
    std::unordered_map<int, int> memo;
    std::unordered_set<int> add = {1, 9, 99};

public:
    int getLengthOfOptimalCompression(std::string s, int k) {
        return dp(s, 0, 'a' + 26, 0, k);
    }

private:
    int dp(const std::string& s, int idx, char lastChar, int lastCharCount, int k) {
        if (k < 0) {
            return INT_MAX / 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.count(lastCharCount) ? 1 : 0);
        } else {
            keepChar = dp(s, idx + 1, s[idx], 1, k) + 1;
        }

        int res = std::min(keepChar, deleteChar);
        memo[key] = res;

        return res;
    }
};

Ставь 👍 и забирай 📚 Базу знаний