สมมติว่าเรามีสตริงตัวเลข s ตามที่รู้ awesome substring คือสตริงย่อยที่ไม่ว่างของ s ที่เราสามารถสลับตัวเลขได้ไม่จำกัดครั้งเพื่อให้กลายเป็น palindrome เราต้องหาความยาวของ awesome substring สูงสุดของ s
เช่น ถ้าอินพุตคือ s = "4353526" ผลลัพธ์จะเป็น 5 เพราะ "35352" เป็น awesome substring ที่ยาวที่สุด เราสามารถทำให้ "35253" เป็น palindrome ได้
วิธีแก้ปัญหา
- n := 0
- pos_map := แมปที่มีคีย์ 0 และค่าเท่ากับขนาดของ s
- max_len := 1
- สำหรับ i ในช่วงขนาดของ s - 1 ถึง 0 ลดทีละ 1:
- n := n XOR (2^s[i])
- ถ้า n อยู่ใน pos_map: max_len := max(max_len, pos_map[n] - i)
- สำหรับ j ในช่วง 0 ถึง 9:
- m := n XOR 2^j
- ถ้า m อยู่ใน pos_map: max_len := max(max_len, pos_map[m] - i)
- ถ้า n ไม่อยู่ใน pos_map: pos_map[n] := i
- return 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
