โปรแกรมนับจำนวน Palindrome ที่ได้จากการ Trim ด้านซ้าย-ขวา (Python)

ปัญหา

กำหนดสตริง s หาจำนวนวิธีที่ได้ palindrome โดยการ "ตัดทิ้ง" ตัวอักษรจากด้านซ้ายและ/หรือขวา (substring ที่เป็น palindrome)

ตัวอย่าง: s="momo" → 6 วิธี
Palindromes: "mom", "omo", "o", "o", "m", "m" (นับซ้ำได้เพราะตำแหน่งต่างกัน)

วิธีแก้: Expand Around Center

ขยายจากจุดกลางทุกตำแหน่ง (odd length และ even length)

อัลกอริทึม

1. ฟังก์ชัน expand(i, j, s): ขยายจากกลาง i,j นับ palindrome ได้กี่อัน
2. วนทุกตำแหน่ง i:
   • expand(i, i) - odd length (center เดียว)
   • expand(i, i+1) - even length (center 2 ตัว)
3. รวมจำนวนทั้งหมด

โค้ด Python

def expand(i, j, s):
    count = 0
    while i >= 0 and j < len(s) and s[i] == s[j]:
        i -= 1
        j += 1
        count += 1
    return count

class Solution:
    def solve(self, s):
        total = 0
        for i in range(len(s)):
            total += expand(i, i, s)      # odd length
            total += expand(i, i + 1, s)  # even length
        return total

# ทดสอบ
ob = Solution()
print(ob.solve("momo"))    # 6
print(ob.solve("aaa"))     # 6 (a,a,a, aa,aa, aaa)
print(ob.solve("abc"))     # 3 (a,b,c)
print(ob.solve(""))        # 0

ความซับซ้อน

• Time: O(n²) - แต่ละ center ขยายได้สูงสุด n
• Space: O(1) - ไม่ใช้พื้นที่เพิ่ม

การทำงานตัวอย่าง "momo"

i=0: expand(0,0)="m" (1), expand(0,1)="" (0)
i=1: expand(1,1)="o" (1), expand(1,2)="" (0)  
i=2: expand(2,2)="m" (1), expand(2,3)="omo" (1)
i=3: expand(3,3)="o" (1), expand(3,4)="" (0)
Total: 1+0+1+0+1+1+1+0 = 6

หมายเหตุ

นับทุก substring ที่เป็น palindrome รวมซ้ำได้ (ตำแหน่งต่างกัน = นับแยก)