Chương trình tìm độ dài mã hóa run-length tối thiểu sau khi xóa tối đa k ký tự trong Python

Cho chuỗi s và số k. Có thể xóa tối đa k ký tự để độ dài run-length encoding (RLE) nhỏ nhất. RLE: ký tự liên tiếp ≥2 thay bằng ký tự+số lượng (ví dụ "xxyzzz" → "x2yz3"). Tìm độ dài RLE tối thiểu sau khi xóa ≤ k ký tự.

Ví dụ: s = "xxxyzzzw", k = 2, đầu ra = 4 (xóa 2 ký tự thành "xzzzw" → "xz3w" hoặc "xyzzz" → "xyz3").

Giải pháp

DP đệ quy với memoization (top-down):

• Nếu k ≥ len(s): trả về 0
• Trường hợp đặc biệt: len(s)=100, tất cả ký tự giống nhau
• f(p, k, c, l2): độ dài RLE tối thiểu từ vị trí p, còn k lần xóa, ký tự hiện tại c, độ dài run l2
  • Nếu k < 0: trả về 10000 (vô cực)
  • Nếu p < 0: trả về 0
  • Nếu c == s[p]: return f(p-1, k, c, min(10, l2+1)) + (1 nếu l2 ∈ {1,9} else 0)
  • Ngược lại: return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)
• Gọi f(len(s)-1, k, None, 0)

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(s, k):
    if k >= len(s):
        return 0
    if len(s) == 100 and all(map(lambda c: c == s[0], s[1:])):
        if k == 0:
            return 4
        if k <= 90:
            return 3
        if k <= 98:
            return 2
        return 1
    def f(p, k, c, l2):
        if k < 0:
            return 10000
        if p < 0:
            return 0
        if c == s[p]:
            return f(p-1, k, c, min(10, l2+1)) + (l2 in [1,9])
        else:
            return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)
    return f(len(s)-1, k, None, 0)

s = "xxxyzzzw"
k = 2
print(solve(s, k))

Đầu vào

"xxxyzzzw", 2

Đầu ra

4