โปรแกรมหาสตริงหลังลบอักขระซ้ำติดกันใน Python

สมมติว่าเรามีสตริง s เราต้องลบอักขระซ้ำติดกันชุดแรกซ้ำๆ จนกว่าจะไม่มีอักขระซ้ำติดกันเหลือ เราต้องหาสตริงสุดท้าย

ตัวอย่าง: s = "xyyyxxz" ผลลัพธ์คือ "z" เพราะ "yyy" เป็นอักขระซ้ำติดกันชุดแรก ถูกลบได้ "xxxz" แล้ว "xxx" ถูกลบเหลือ "z"

ขั้นตอนการแก้ปัญหา

1. สร้างสแต็ก stack ว่าง, i = 0
2. วนลูป while i < len(s):
   • ถ้า stack ไม่ว่าง และ stack[-1] == s[i]:
     • x = stack.pop()
     • วนลูป while i < len(s) และ x == s[i]: i += 1
     • i -= 1
   • อื่นๆ: stack.append(s[i])
   • i += 1
3. คืนค่า "".join(stack)

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

class Solution:
    def solve(self, s):
        stack = []
        i = 0
        while i < len(s):
            if stack and stack[-1] == s[i]:
                x = stack.pop()
                while i < len(s) and x == s[i]:
                    i += 1
                i -= 1
            else:
                stack.append(s[i])
            i += 1
        return "".join(stack)

ob = Solution()
s = "xyyyxxz"
print(ob.solve(s))  # Output: z

อินพุต / เอาต์พุต

Input: "xyyyxxz"

Output: z