สมมติว่าเรามีสตริงตัวเลข s อย่างที่เราทราบดีว่าสตริงย่อยที่ยอดเยี่ยมคือสตริงย่อยที่ไม่ว่างเปล่าของ s ซึ่งเราสามารถทำการสลับจำนวนเท่าใดก็ได้เพื่อทำให้มันเป็นพาลินโดรม เราต้องหาความยาวของความยาวสูงสุดของสตริงย่อยที่น่ากลัวของ s
ดังนั้น หากอินพุตเป็นเหมือน s ="4353526" ผลลัพธ์จะเป็น 5 เพราะ "35352" เป็นสตริงย่อยที่ยาวที่สุด เราสามารถสร้าง "35253" palindrome ได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
น :=0
-
pos_map :=แผนที่ที่มีคีย์ 0 และค่าที่สอดคล้องกันคือขนาดของ s
-
max_len :=1
-
สำหรับฉันในช่วงขนาด s - 1 ถึง 0, ลดลง 1 ทำ
-
n :=n XOR (2^s[i])
-
ถ้า n มีอยู่ใน pos_map แล้ว
-
max_len :=สูงสุดของ max_len และ pos_map[n]-i
-
-
สำหรับ j ในช่วง 0 ถึง 9 ทำ
-
m :=n XOR 2^j
-
ถ้า m อยู่ใน pos_map แล้ว
-
max_len :=สูงสุดของ max_len และ pos_map[m]-i
-
-
-
ถ้าไม่ได้อยู่ใน pos_map แล้ว
-
pos_map[n] :=ผม
-
-
-
ส่งคืน max_len
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(s):
n = 0
pos_map = {0:len(s)}
max_len = 1
for i in range(len(s)-1, -1, -1):
n = n ^ (1 << int(s[i]))
if n in pos_map:
max_len = max(max_len, pos_map[n]-i)
for j in range(10):
m = n ^ (1 << j)
if m in pos_map:
max_len = max(max_len, pos_map[m]-i)
if n not in pos_map:
pos_map[n] = i
return max_len
s = "4353526"
print(solve(s)) อินพุต
"4353526"
ผลลัพธ์
5
