Chương trình tìm độ dài tối thiểu chuỗi sau khi xóa đầu/cuối giống nhau trong Python

Cho chuỗi s chỉ chứa 'a', 'b', 'c'. Lặp lại: chọn tiền tố không rỗng toàn ký tự giống nhau và hậu tố không rỗng toàn ký tự giống nhau (cùng ký tự, không giao nhau), xóa cả hai. Tìm độ dài nhỏ nhất có thể.

Ví dụ: s = "aabccabba" → 3. Bước 1: xóa "aa" (đầu) và "a" (cuối) → "bccabb". Bước 2: xóa "b" và "bb" → "cca" (độ dài 3).

Giải thuật (Deque)

1. Đưa s vào deque.
2. Trong khi độ dài > 1 và ký tự đầu == ký tự cuối:
   • chk = s[0].
   • Xóa liên tiếp từ đầu cho bằng chk.
   • Xóa liên tiếp từ cuối cho bằng chk.
3. Trả về độ dài deque còn lại.

Ví dụ minh họa

from collections import deque

def solve(s):
    s = deque(s)
    while len(s) > 1 and s[0] == s[-1]:
        chk = s[0]
        while s and s[0] == chk:
            s.popleft()
        while s and s[-1] == chk:
            s.pop()
    return len(s)

s = "aabccabba"
print(solve(s))

Đầu vào

"aabccabba"

Đầu ra

3