โปรแกรมหาสตริงที่ดี (Good String) ใน Python

ภาพรวม

สตริง "ดี" (Good String) หมายถึงสตริงที่ไม่มีตัวอักษรติดกัน 2 ตัวที่เป็นตัวอักษรเดียวกันแต่ต่าง case (พิมพ์เล็ก-พิมพ์ใหญ่) เช่น 'aA' หรือ 'Bb' โปรแกรมจะลบคู่ตัวอักษรแบบนี้ซ้ำๆ จนกว่าสตริงจะกลายเป็น "ดี"

ตัวอย่าง

อินพุต: "popPpulaBbr"

กระบวนการ: ลบ 'pP' หรือ 'Pp' และลบ 'Bb' → ผลลัพธ์ "popular"

ขั้นตอนการแก้ปัญหา (ใช้ Stack)

1. สร้างลิสต์ว่าง res ใช้เป็น Stack
2. วนลูปผ่านแต่ละตัวอักษร ch ในสตริง s:
   • ถ้า res ไม่ว่าง และตัวอักษรสุดท้ายใน res เป็นตัวอักษรเดียวกับ ch แต่ต่าง case (เช่น 'a' กับ 'A') ให้ pop() ตัวสุดท้ายออก
   • มิฉะนั้น ให้ append(ch) เข้า res
3. รวมสมาชิกใน res เป็นสตริงและคืนค่า

ตัวอย่างโค้ด (Python)

def solve(s):
    res = []
    for ch in s:
        if res and res[-1] != ch and res[-1].lower() == ch.lower():
            res.pop()
        else:
            res.append(ch)
    return ''.join(res)

s = "popPpulaBbr"
print(solve(s))

อินพุต

"popPpulaBbr"

เอาต์พุต

popular

ความซับซ้อน

• เวลา: O(n) โดย n = ความยาวสตริง
• พื้นที่: O(n) สำหรับ Stack