โปรแกรมหาความยาววงเล็บถูกต้องที่ยาวที่สุดใน Python

ได้รับสตริง s ประกอบด้วย ( และ ) เท่านั้น หา ความยาวของ substring ที่เป็นวงเล็บถูกต้อง (valid parentheses) ยาวที่สุด

ตัวอย่าง

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

Output: 6 (substring "(())()")

แนวทางแก้ปัญหา

ใช้ Stack เก็บ index:

1. เริ่ม stack = [-1] (base index)
2. วนอ่านตัวอักษร index i:
   • ถ้า ( → push i
   • ถ้า ):
     • pop stack
     • ถ้า stack ไม่ว่าง → ความยาว valid = i - stack[-1] อัปเดตคำตอบ
     • ถ้า stack ว่าง → push i เป็น base ใหม่

การใช้งาน (Python)

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

ความซับซ้อน

• Time Complexity: O(N)
• Space Complexity: O(N)

วิธีนี้ง่ายและมีประสิทธิภาพดีกว่าวิธี DP แบบเดิม