Сложность: hard
Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками.
Пример:
Input: s = "(()"
Output: 2
👨💻 Алгоритм:
1️⃣В этом подходе мы рассматриваем каждую возможную непустую подстроку чётной длины из заданной строки и проверяем, является ли она корректной строкой скобок. Для проверки корректности мы используем метод стека.
2️⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной.
3️⃣Таким образом, мы повторяем процесс для каждой возможной подстроки и продолжаем сохранять длину самой длинной найденной корректной строки.
😎 Решение:
def is_valid(s: str) -> bool:
stack = []
for char in s:
if char == '(':
stack.append('(')
elif stack and stack[-1] == '(':
stack.pop()
else:
return False
return len(stack) == 0
def longest_valid_parentheses(s: str) -> int:
maxlen = 0
for i in range(len(s)):
for j in range(i + 2, len(s) + 1, 2):
substring = s[i:j]
if is_valid(substring):
maxlen = max(maxlen, j - i)
return maxlen
Ставь 👍 и забирай 📚 Базу знаний