32. Longest Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses/description/?envType=featured-list&envId=top-google-questions

input :

• s

output :

• 가장 길이가 긴 parentheses 부분 문자열의 길이를 출력하시오.

조건 :

• "()"의 형태가 valid 하여야 한다.

---

Solution explain : Solution1

idea

• stack을 이용하여 부분문자열이 끊기는 부분을 저장하자.
• ")"이 입력 될 때, stack이 있고, top의 값이 "("이라면 해당 idx값을 stack에서 제거한다.
• 그렇지 않은 경우에는 idx를 계속 입력한다.
• stack에 저장되어 있는 값들은 idx값들이고 인접한 두 값 끼리의 차이 - 1 만큼의 valid한 부분문자열이 존재할 것이다.

주의

• 뒤에서부터 계산을 하는 것이 편하다.

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        unpair_idxes = []
        for i in range(len(s)):
            item = s[i]
            if item == ")":
                if unpair_idxes and s[unpair_idxes[-1]] == "(":
                        unpair_idxes.pop()
                        continue
            unpair_idxes.append(i)

        ret = 0
        prev = len(s)
        for item in unpair_idxes[::-1]:
            ret = max(ret, prev - 1 - item)
            prev = item
        ret = max(ret, prev)
        return ret

s = Solution()
print(s.longestValidParentheses("())"))
print(s.longestValidParentheses(")()())"))
print(s.longestValidParentheses("()(()"))