Задача: 32. Longest Valid Parentheses
Сложность: hard

Дана строка, содержащая только символы '(' и ')'. Верните длину самой длинной подстроки с корректными (правильно сформированными) скобками.

Пример:

Input: s = "(()"
Output: 2

👨‍💻 Алгоритм:

1⃣В этом подходе мы рассматриваем каждую возможную непустую подстроку чётной длины из заданной строки и проверяем, является ли она корректной строкой скобок. Для проверки корректности мы используем метод стека.

2⃣Каждый раз, когда мы встречаем символ ‘(’, мы кладём его в стек. Для каждого встреченного символа ‘)’ мы извлекаем из стека символ ‘(’. Если символ ‘(’ недоступен в стеке для извлечения в любой момент или если в стеке остались элементы после обработки всей подстроки, подстрока скобок является некорректной.

3⃣Таким образом, мы повторяем процесс для каждой возможной подстроки и продолжаем сохранять длину самой длинной найденной корректной строки.

😎 Решение:

func isValid(_ s: String) -> Bool {
    var stack = [Character]()
    for char in s {
        if char == "(" {
            stack.append("(")
        } else if !stack.isEmpty && stack.last == "(" {
            stack.removeLast()
        } else {
            return false
        }
    }
    return stack.isEmpty
}

func longestValidParentheses(_ s: String) -> Int {
    var maxlen = 0
    for i in 0..<s.count {
        for j in stride(from: i + 2, through: s.count, by: 2) {
            let start = s.index(s.startIndex, offsetBy: i)
            let end = s.index(s.startIndex, offsetBy: j)
            let substring = String(s[start..<end])
            if isValid(substring) {
                maxlen = max(maxlen, j - i)
            }
        }
    }
    return maxlen
}

Ставь 👍 и забирай 📚 Базу знаний