Giả sử chúng ta có một chuỗi s chỉ có ba ký tự 'a', 'b' và 'c'. Chúng tôi sẽ áp dụng thuật toán sau trên chuỗi bất kỳ số lần nào -
-
Chọn một tiền tố không trống từ các s mà tất cả các ký tự trong tiền tố đều giống nhau.
-
Chọn một hậu tố không trống từ các s mà tất cả các ký tự trong hậu tố đều giống nhau.
-
Tiền tố và hậu tố không tách rời nhau.
-
Các ký tự từ tiền tố và hậu tố phải giống nhau.
-
Xóa cả tiền tố và hậu tố khỏi s.
Cuối cùng, chúng ta phải tìm độ dài tối thiểu của s sau khi thực hiện thao tác trên bất kỳ số lần nào (có thể là 0 lần).
Vì vậy, nếu đầu vào là s ="aabccabba", thì đầu ra sẽ là 3 vì lúc đầu chúng ta có thể chọn tiền tố ="aa" và hậu tố ="a", để chuỗi sau khi loại bỏ là "bccabb", sau đó chọn tiền tố ="b" và hậu tố "bb", vì vậy chuỗi sau khi xóa là "cca", có độ dài 3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
s:=tạo hàng đợi với s
-
trong khi kích thước của s> 1 và s [0] là phần tử cuối cùng của s, do
-
chk:=s [0]
-
trong khi s và s [0] giống nhau, hãy làm
-
xóa phần tử bên trái khỏi s
-
-
trong khi s không trống và phần tử cuối cùng của s giống với chk, do
-
xóa phần tử cuối cùng khỏi s
-
-
-
kích thước trả về của s
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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