Chương trình tìm độ dài chuỗi con xóa được nhưng t vẫn là dãy con của s trong Python

Cho chuỗi s và t (t là dãy con của s). Tìm độ dài lớn nhất của chuỗi con liên tiếp có thể xóa khỏi s sao cho t vẫn là dãy con.

Ví dụ: s="xyzxyxz", t="yz" → 4 (xóa "zxyx" hoặc đoạn giữa).

Giải thuật (Tìm vị trí match trái nhất và phải nhất)

1. Duyệt trái→phải tìm match đầu tiên của t trong s → lưu chỉ số vào left[]. Phần đuôi sau match cuối = c1.
2. Duyệt phải→trái tìm match cuối cùng của t trong s → lưu vào right[]. Phần đầu trước match đầu = c2.
3. Xét xóa đoạn giữa: max(right[i+1] - left[i] - 1) cho i=0..len(t)-2 → c3.
4. Kết quả = max(c1, c2, c3).

Ví dụ minh họa

class Solution:
    def solve(self, s, t):
        left, right = [], []
        j = 0
        # Match trái nhất
        for i, ch in enumerate(s):
            if ch == t[j]:
                left.append(i)
                j += 1
                if j == len(t):
                    c1 = len(s) - i - 1
                    break
        # Match phải nhất
        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:
                    c2 = i
                    break
        # Xóa đoạn giữa
        c3 = -1
        for i in range(len(t) - 1):
            c3 = max(c3, right[i + 1] - left[i] - 1)
        return max(c1, c2, c3)

ob = Solution()
s = "xyzxyxz"
t = "yz"
print(ob.solve(s, t))  # Output: 4

Đầu vào / Đầu ra

Input: "xyzxyxz", "yz"

Output: 4