Chương trình đếm số dấu ngoặc đơn tối thiểu cần xóa để chuỗi đúng bằng Python

Cho chuỗi dấu ngoặc đơn, tìm số lượng dấu ngoặc tối thiểu cần xóa để chuỗi trở nên đúng (mọi dấu mở đều được đóng).

Ví dụ: "(()))(" → 2 (chuỗi đúng là "(())", xóa ")(").

Quy trình giải quyết

1. Khởi tạo total = 0 (số dấu mở chưa khớp), temp = 0 (số dấu đóng thừa).
2. Duyệt qua chuỗi:
   • Nếu là '(', tăng total.
   • Nếu là ')' và total > 0, giảm total.
   • Ngược lại, tăng temp.
3. Trả về total + temp.

Ví dụ mã nguồn

class Solution:
    def solve(self, s):
        total = 0
        temp = 0
        for p in s:
            if p == "(":
                total += 1
            elif p == ")" and total:
                total -= 1
            else:
                temp += 1
        return total + temp

ob1 = Solution()
string = "(()))("
print(ob1.solve(string))  # Output: 2

Đầu vào

"(()))("

Đầu ra

2