Chương trình tìm độ dài chuỗi ngoặc hợp lệ dài nhất trong Python

Cho chuỗi s chỉ chứa ( và ). Tìm độ dài chuỗi con ngoặc hợp lệ (well-formed) dài nhất.

Ví dụ: "))(())())" → kết quả 6 (chuỗi con "(())()").

Giải thuật (Stack lưu chỉ số)

1. Khởi tạo stack = [-1], ans = 0.
2. Duyệt i từ 0 đến len(s)-1:
   • Nếu s[i] == '(': push i.
   • Ngược lại (gặp ')'):
     • Pop stack.
     • Nếu stack không rỗng: ans = max(ans, i - stack[-1]).
     • Nếu stack rỗng: push i (đánh dấu vị trí ngoặc đóng dư).

Ví dụ minh họa

class Solution:
    def solve(self, s):
        stack = [-1]
        ans = 0
        for i, ch in enumerate(s):
            if ch == '(':
                stack.append(i)
            else:
                stack.pop()
                if stack:
                    ans = max(ans, i - stack[-1])
                else:
                    stack.append(i)
        return ans

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

Đầu vào / Đầu ra

Input: "))(())())"

Output: 6