โปรแกรมหาความยาว substring ที่ลบได้แต่ t ยังเป็น subsequence ใน Python

ได้รับสตริง s และ t โดย t เป็น subsequence ของ s หา ความยาว substring สูงสุดที่ลบออกจาก s ได้ โดยที่ t ยังคงเป็น subsequence

ตัวอย่าง

Input: s = "xyzxyxz", t = "yz"

Output: 4

ลบ substring ความยาว 4 ได้ (เช่น "zxyx" หรือส่วนอื่นๆ)

แนวทางแก้ปัญหา

หาตำแหน่ง ซ้ายสุด (left) และ ขวาสุด (right) ที่ match แต่ละตัวของ t:

1. left[i] = index ใน s ของ t[i] ตัวแรกจากซ้าย
2. right[i] = index ใน s ของ t[i] ตัวสุดท้ายจากขวา
3. โอกาสลบ substring ยาวที่สุด 3 กรณี:
   • หน้า left[0] → ความยาว left[0]
   • หลัง right[-1] → ความยาว len(s) - right[-1] - 1
   • ระหว่าง left[i] และ right[i+1] → right[i+1] - left[i] - 1

การใช้งาน (Python)

class Solution:
    def solve(self, s, t):
        left = []
        right = []
        
        # Leftmost matches
        j = 0
        for i, ch in enumerate(s):
            if ch == t[j]:
                left.append(i)
                j += 1
                if j == len(t):
                    break
        
        # Rightmost matches
        j = len(t) - 1
        for i in range(len(s) - 1, -1, -1):
            if s[i] == t[j]:
                right.insert(0, i)
                j -= 1
                if j == -1:
                    break
        
        # 3 cases
        c1 = left[0]                    # prefix
        c2 = len(s) - right[-1] - 1     # suffix
        c3 = max(right[i + 1] - left[i] - 1 for i in range(len(t) - 1))  # middle
        
        return max(c1, c2, c3)

# ทดสอบ
ob = Solution()
print(ob.solve("xyzxyxz", "yz"))  # Output: 4

ความซับซ้อน

• Time Complexity: O(|s| + |t|)
• Space Complexity: O(|t|)