FAANG 인터뷰 질문| 가장 긴 유효한 괄호

문자 '(' 및 ')'만 포함하는 문자열이 주어지면 가장 긴 유효한(올바른 형식의) 괄호 하위 문자열의 길이를 찾습니다.

예 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".


예 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".


예 3:

Input: s = ""
Output: 0


제약:
  • 0 <= s.길이 <= 3 * 104
  • s[i]는 '(' 또는 ')'입니다.

  • 해결책 1:




    # O(n) time | O(n) space - where n is the length of the input string
    def longestBalancedSubstring(string):
        stack = [-1]
        longest = 0
        for idx in range(len(string)):
            ch = string[idx]
            if ch == "(":
                stack.append(idx)
            else:
                stack.pop()
                if len(stack) == 0:
                    stack.append(idx)
                else:
                    top = stack[-1]
                    longest = max(longest, idx - top)
    
    
        return longest
    


    더 나은 솔루션




    # O(n) time | O(1) space - where n is the length of the input string
    def longestBalancedSubstring(string):
        return max(
                get_longest_sub_string_count(string, True),
                get_longest_sub_string_count(string, False)
            )
    
    def get_longest_sub_string_count(string, left_to_right):
        open_ch= "(" if left_to_right else ")"
        step = 1 if left_to_right else -1
        idx = 0 if left_to_right else len(string) - 1
        open_count = 0
        close_count = 0
        longest = 0
        while idx > -1 and idx < len(string):
            ch = string[idx]
            if ch == open_ch:
                open_count +=1
            else:
                close_count += 1
    
            if close_count == open_count:
                longest = max(longest, open_count*2)
            elif close_count > open_count:
                open_count = 0
                close_count = 0
    
            idx += step
    
    
        return longest
    
    

    좋은 웹페이지 즐겨찾기