32. Longest Valid Parentheses

[zeikar]

Problem link

https://leetcode.com/problems/longest-valid-parentheses

Problem Summary

괄호로 된 문자열이 주어지고 valid한 괄호 부분 문자열의 최대 길이를 구하는 문제.

Solution

딱 보니 스택이 생각난다.

( 괄호가 보이면 스택에 현재 인덱스를 넣고 ) 괄호가 보이면 스택에서 빼는 방식이다. 뺄 때 현재 인덱스에서 스택의 마지막 인덱스를 빼면 길이가 된다.
여기서 ()() 같이 서로 이어져야 되므로 스택은 기본적으로 1개의 원소가 들어가 있어야 한다. 그리고 스택에서 뺐을 때 비어 있지 않아야 valid 한 부분 문자열이 된다.

Source Code

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = []
        max_len = 0

        stack.append(-1)
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if len(stack) == 0:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        return max_len