Leetcode 32. Longest Valid Parentheses

문제

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses 
substring

( 와 ) 로 이루어진 문자열이 주어진다.
문자열의 부분 문자열중 올바른 괄호 쌍의 최대 길이를 구하시오

예시

(()((())
- 여기서 올바른 괄호 쌍 중 가장 긴 부분 문자열은 (()) 이다.
- 4가 답이다.

제한

• $0 <= s.length <= 3 * 10^4$
• 문자열 s는 ( 와 ) 로만 구성된다.

풀이

어떤 경우에 올바르지 못한 괄호쌍이 생겨날까?

1. 앞에 여는 괄호가 없는 상태에서 닫는 괄호가 나온다.
2. 맞는 쌍이 없는 여는 괄호

이 경우들을 트래킹 할수 있다면 이 문제를 해결할수 있다.

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stck = [-1]
        cnt = 0

        for ind, ch in enumerate(s):
            if ch == '(':
                stck.append(ind)
            else:
                stck.pop()
                if not stck:
                    stck.append(ind)
                else:
                    cnt = max(cnt, ind - stck[-1])

        return cnt