โปรแกรมหาความยาวของลำดับย่อยที่มีวงเล็บสมดุลมากที่สุดใน Python

สมมติว่าเรามีสตริง s ที่มีวงเล็บ "(" และ ")" เราต้องการหาความยาวของลำดับย่อย (subsequence) ที่มีวงเล็บสมดุล (balanced brackets) มากที่สุด

ตัวอย่างเช่น หาก s = "())(()("` ผลลัพธ์จะเป็น 4 เนื่องจากเราสามารถเลือก subsequence เป็น "()()"

1. res = 0, n = len(s), close = 0
2. วนลูป i จาก n-1 ถึง 0 (ถอยหลัง):
   • หาก s[i] == ")" ให้ close += 1
   • มิฉะนั้น (เป็น "("):
     • หาก 0 ให้ close -= 1 และ res += 2
3. คืนค่า res

ตัวอย่างโค้ด Python

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

อินพุต

"())(()("

เอาต์พุต

4