Chương trình tìm độ dài dãy con ngoặc cân bằng dài nhất trong Python

Cho chuỗi s chỉ chứa '(' và ')', tìm độ dài dãy con (subsequence, không cần liên tiếp) cân bằng ngoặc dài nhất.

Ví dụ: s = "())(()(" → kết quả 4 (dãy con "()()").

Giải thuật (Duyệt ngược - O(n))

1. Khởi tạo res = 0, close = 0.
2. Duyệt từ n-1 xuống 0:
   • Nếu : close += 1.
   • Ngược lại (là '('): nếu 0: , (ghép cặp).
3. Trả về res.

Ví dụ minh họa

class Solution:
    def solve(self, s):
        res = 0
        n = len(s)
        close = 0
        for i in range(n - 1, -1, -1):
            if s[i] == ")":
                close += 1
            else:
                if close > 0:
                    close -= 1
                    res += 2
        return res

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

Đầu vào

"())(()("

Đầu ra

4