1531. String Compression II
Дана строка 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.
C# решение
сопоставлено/оригинал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;
}
}C++ решение
auto-draft, проверить перед отправкой#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;
}
}Java решение
сопоставлено/оригинал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;
}
}JavaScript решение
сопоставлено/оригинал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;
}
}Python решение
сопоставлено/оригинал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 resGo решение
сопоставлено/оригинал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
Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.
Для определения состояния DP используем следующие параметры: количество пройденных символов (чтобы знать, какой символ обрабатывать следующим), последний добавленный символ в сжатую строку (чтобы определить изменение сжатия при добавлении нового символа), количество последнего символа (для правильного изменения длины сжатия при добавлении символа) и количество оставшихся символов, которые можно удалить.
Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.