โปรแกรมหาความยาวน้อยที่สุดของ Run-Length Encoding แบบ Lossy ใน Python

สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s และค่า k พิจารณา Run-Length Encoding (RLE): ตัวอักษรซ้ำติดกันเข้ารหัสเป็น count+char เช่น "aaabbc" → "3a2bc" (ไม่เขียน 1c) เราสามารถลบ k ตัวอักษรติดกันออกจาก s ก่อน แล้วหาความยาว RLE น้อยที่สุด

ตัวอย่าง: s = "xxxxxyyxxxxxzzxxx", k = 2 ผลลัพธ์ 6 (ลบ "zz" ได้ "5x2y8x" ความยาว 6)

ขั้นตอนการแก้ปัญหา (Prefix/Suffix + Sliding Window)

1. ฟังก์ชัน calc_cost(l) ความยาว RLE ของกลุ่มยาว l:
   • l == 0: 0
   • l == 1: 1
   • อื่นๆ: len(str(l)) + 1
2. ฟังก์ชัน prefix(s) สร้าง prefix sum ของ RLE cost และความยาวกลุ่มสุดท้าย
3. สร้าง pre = prefix(s), suf = prefix(s[::-1])[::-1]
4. ลองลบช่วงยาว k ทุกตำแหน่ง i:
   • j = i + k
   • รวม cost = pre[i][0] + suf[j][0]
   • ถ้าตัวอักษรขอบ c1 == c2: บวก calc_cost(pre[i][1] + suf[j][1])
   • อื่นๆ: บวก calc_cost(pre[i][1]) + calc_cost(suf[j][1])
   • อัปเดตค่าน้อยที่สุด
5. คืนค่าค่าน้อยที่สุด

ตัวอย่างโค้ด Python

def calc_cost(l):
    if l == 0:
        return 0
    if l == 1:
        return 1
    else:
        return len(str(l)) + 1

class Solution:
    def solve(self, s, k):
        def prefix(s):
            pre = [[0, 0]]
            last = None
            for c in s:
                if c == last:
                    pre.append([pre[-1][0], pre[-1][1] + 1])
                else:
                    pre.append([pre[-1][0] + calc_cost(pre[-1][1]), 1])
                last = c
            return pre
        pre = prefix(s)
        suf = prefix(s[::-1])[::-1]
        ans = float("inf")
        for i in range(len(s) - k + 1):
            j = i + k
            left, midl = pre[i]
            right, midr = suf[j]
            cost = left + right
            c1 = s[i - 1] if i > 0 else None
            c2 = s[j] if j < len(s) else None
            if c1 == c2:
                cost += calc_cost(midl + midr)
            else:
                cost += calc_cost(midl) + calc_cost(midr)
            ans = min(ans, cost)
        return ans

ob = Solution()
s = "xxxxxyyxxxxxzzxxx"
print(ob.solve(s, 2))  # Output: 6

อินพุต / เอาต์พุต

Input: s = "xxxxxyyxxxxxzzxxx", k = 2

Output: 6