โปรแกรมหาจำนวนการดำเนินการน้อยสุดทำให้สตริงหนึ่งเป็น substring ของอีกสตริงใน Python

ให้สตริง s และ t หาจำนวนการเปลี่ยนตัวอักษรน้อยสุดใน s ใดๆ ทำให้ t เป็น substring ของ s

ตัวอย่าง: s="abbpqr", t="bbxy" → 2 (เปลี่ยน "bbpq" → "bbxy": p→x, q→y)

อัลกอริธึม Sliding Window

• สไลด์หน้าต่างขนาด len(t) บน s
• นับตัวอักษรที่ต่างกันในแต่ละหน้าต่าง
• หาค่าน้อยสุด

การนำไปใช้

class Solution:
    def solve(self, s, t):
        k, n = len(t), len(s)
        ans = 10**10
        for i in range(n - k + 1):
            ss = s[i:i+k]
            diff = sum(ss[j] != t[j] for j in range(k))
            ans = min(ans, diff)
        return ans

ob = Solution()
print(ob.solve("abbpqr", "bbxy"))  # 2