Xóa Ký Tự Trùng Lặp Liền Kề (Remove Adjacent Duplicates) Trong Python

Cho chuỗi S chữ thường. Lặp lại: tìm 2 ký tự liền kề giống nhau, xóa cả 2. Dừng khi không còn cặp nào. Trả về chuỗi kết quả (duy nhất).

Ví dụ: "abbacaca" → xóa bb → "aacaca" → xóa aa → "caca" → dừng.

Thuật toán Stack (Tối ưu)

1. Khởi tạo stack rỗng
2. Duyệt từng ký tự c trong S:
   • Nếu stack không rỗng và stack[-1] == c: stack.pop() (xóa cặp)
   • Ngược lại: stack.append(c)
3. Kết quả = "".join(stack)

Ví dụ (Python)

class Solution(object):
    def removeDuplicates(self, S):
        stack = []
        for c in S:
            if stack and stack[-1] == c:
                stack.pop()
            else:
                stack.append(c)
        return "".join(stack)

ob1 = Solution()
print(ob1.removeDuplicates("abbacaca"))  # "caca"
print(ob1.removeDuplicates("azxxzy"))    # "ay"
print(ob1.removeDuplicates("aababa"))    # "baba"

Độ phức tạp

• Thời gian: O(n) - mỗi ký tự push/pop tối đa 1 lần
• Không gian: O(n) - stack

Đầu vào / Đầu ra

Input:  "abbacaca"
Output: "caca"

Bài toán mở rộng

LeetCode 1209: Xóa k ký tự liền kề giống nhau. Dùng stack lưu (char, count).