Chương trình tìm chuỗi sau khi xóa các ký tự trùng lặp liên tiếp bằng Python

Cho chuỗi s, lặp lại việc xóa nhóm ký tự trùng lặp liên tiếp đầu tiên. Trả về chuỗi cuối cùng.

Ví dụ: s = "xyyyxxz" → "z" (xóa "yyy" → "xxxz" → xóa "xxx" → "z").

Quy trình giải quyết

1. Dùng ngăn xếp stack.
2. Duyệt qua chuỗi với chỉ số i.
3. Nếu đỉnh ngăn xếp bằng s[i]:
   • Lấy x = stack.pop().
   • Bỏ qua tất cả các x liên tiếp trong chuỗi.
   • Giảm i đi 1 để kiểm tra lại ký tự tiếp theo.
4. Ngược lại, đẩy s[i] vào ngăn xếp.
5. Trả về chuỗi nối từ ngăn xếp.

Ví dụ mã nguồn

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

Đầu vào

"xyyyxxz"

Đầu ra

z