Giả sử chúng ta có một văn bản. Ta phải tìm k lớn nhất có thể sao cho tồn tại a [1], a [2], ..., a [k] sao cho:Mỗi a [i] là một chuỗi không rỗng; Nối a [1] + a [2] + ... + a [k] của chúng bằng đoạn văn đã cho; Đối với tất cả các i trong phạm vi từ 1 đến k, a [i] =a [{k + 1 - i}].
Vì vậy, nếu đầu vào giống như "antaprezatepzapreanta", thì đầu ra sẽ là 11, vì chúng ta có thể chia nó như "(a) (nt) (a) (pre) (za) (tpe) (za) (pre) ( a) (nt) (a) ".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
start:=0, end:=độ dài văn bản - 1
-
khởi tạo temp1 và temp2 bằng chuỗi trống
-
ans =1 khi độ dài của văn bản là lẻ, ngược lại là 0
-
trong khi bắt đầu
-
temp1:=temp1 + text [start]
-
temp2:=text [end] + temp2
-
nếu temp1 giống với temp2 thì -
-
đặt temp1 và temp2 dưới dạng chuỗi trống
-
ans:=ans + 2
-
-
start:=start + 1
-
end:=end - 1
-
-
nếu độ dài văn bản là chẵn và (temp1 hoặc temp2 không trống)
-
ans:=ans + 1
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution(object):
def longestDecomposition(self, text):
start = 0
end = len(text)-1
temp1 = ""
temp2 = ""
ans = 1 if len(text) & 1 else 0
while start<end:
temp1+=text[start]
temp2 = text[end]+temp2
if temp1 == temp2:
temp1 = temp2 = ""
ans+=2
start+=1
end-=1
if len(text)%2 == 0 and(temp1 or temp2):
ans += 1
return ans
ob = Solution()
print(ob.longestDecomposition("antaprezatepzapreanta")) Đầu vào
"antaprezatepzapreanta"
Đầu ra
11