เกมจัดเรียงสตริงให้เป็นพาลินโดรม ผู้ทำได้ก่อนชนะ
สตริง S ตัวพิมพ์เล็ก สองผู้เล่นสลับกันเล่น กฎ: ผู้เล่นชนะได้ทันทีหากในตอนของเขา สามารถจัดเรียงตัวอักษรของสตริงให้เป็นพาลินโดรมได้ (ไม่ต้องลบตัวอักษร) ผู้เล่น 1 เริ่มก่อน ทั้งคู่เล่นอย่างเหมาะสมที่สุด
ตัวอย่าง: "pqpppq" → ผู้เล่น 1 ชนะ (จัดเป็น "ppqqpp")
สังเกตสำคัญ
สตริงจัดเป็นพาลินโดรมได้ ⟺ จำนวนตัวอักษรที่มีความถี่คี่ ≤ 1
- ถ้าตอนเริ่มต้นเป็นพาลินโดรมได้แล้ว (odd_count = 0) → ผู้เล่น 1 ชนะทันที
- ถ้า odd_count เป็นคี่ → ผู้เล่น 1 ชนะ (เพราะเขาเล่นก่อนและสามารถบังคับให้สถานะเป็นพาลินโดรมได้)
- ถ้า odd_count เป็นคู่ (>0) → ผู้เล่น 2 ชนะ
โค้ดตัวอย่าง Python
def who_is_the_winner(sequence):
freq = [0]*26
for ch in sequence:
freq[ord(ch)-ord('a')] += 1
odd = sum(1 for f in freq if f % 2 == 1)
return 1 if (odd == 0 or odd % 2 == 1) else 2
print("Player:", who_is_the_winner("pqpppq")) # Player: 1
