Chương trình tìm chuỗi ngắn nhất sau khi xóa các cặp bit liền kề khác nhau trong Python

Cho chuỗi nhị phân s, có thể xóa bất kỳ hai ký tự liền kề nào nếu chúng khác nhau. Tìm độ dài chuỗi nhỏ nhất có thể đạt được sau khi thực hiện phép toán nhiều lần tùy ý.

Ví dụ, s = "1100011", đầu ra 1 (xóa "10" -> "10011", xóa "10" -> "011", xóa "01" -> "1").

Các bước giải quyết (dùng stack):

• stack := danh sách rỗng.
• Duyệt từng ký tự c trong s:
  • Nếu stack rỗng hoặc đỉnh stack == c, đẩy c vào stack.
  • Ngược lại (khác nhau), lấy đỉnh ra khỏi stack.
• Trả về độ dài stack.

Ví dụ minh họa

class Solution:
    def solve(self, s):
        stack = []
        for c in s:
            if not stack or stack[-1] == c:
                stack.append(c)
            elif stack[-1] != c:
                stack.pop()
        return len(stack)

ob = Solution()
print(ob.solve("1100011"))

Đầu vào

"1100011"

Đầu ra

1