สมมติว่าเรามีสตริง s ที่มีอักขระเพียงสามตัว 'a', 'b' และ 'c' เราจะใช้อัลกอริทึมต่อไปนี้กับสตริงกี่ครั้งก็ได้ -
-
เลือกคำนำหน้าที่ไม่เว้นว่างจาก s โดยที่อักขระทั้งหมดในคำนำหน้าเหมือนกัน
-
เลือกคำต่อท้ายที่ไม่เว้นว่างจาก s โดยที่อักขระทั้งหมดในส่วนต่อท้ายเหมือนกัน
-
คำนำหน้าและส่วนต่อท้ายไม่ปะติดปะต่อกัน
-
อักขระจากคำนำหน้าและคำต่อท้ายต้องเหมือนกัน
-
ลบทั้งคำนำหน้าและส่วนต่อท้ายออกจาก s
สุดท้าย เราต้องค้นหาความยาวต่ำสุดของ s หลังจากดำเนินการดังกล่าวเป็นจำนวนเท่าใดก็ได้ (อาจเป็นศูนย์ครั้ง)
ดังนั้นหากอินพุตเป็น s ="aabccabba" ผลลัพธ์จะเป็น 3 เพราะในตอนแรกเราสามารถเลือกคำนำหน้า ="aa" และคำต่อท้าย ="a" เพื่อให้สตริงหลังการลบเป็น "bccabb" ได้ select prefix ="b" และ suffix "bb" ดังนั้น string หลังการลบคือ "cca" ซึ่งมีความยาว 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
s :=จัดคิวด้วย s
-
ในขณะที่ขนาดของ s> 1 และ s[0] เป็นองค์ประกอบสุดท้ายของ s ให้ทำ
-
chk :=s[0]
-
ในขณะที่ s และ s[0] เหมือนกัน ทำ
-
ลบองค์ประกอบด้านซ้ายออกจาก s
-
-
ในขณะที่ s ไม่ว่างและองค์ประกอบสุดท้ายของ s เหมือนกับ chk ให้ทำ
-
ลบองค์ประกอบสุดท้ายออกจาก s
-
-
-
ขนาดส่งคืนของ s
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
"aabccabba"
ผลลัพธ์
3
