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

Учитывая строку, содержащую только символы «(» и «)», верните длину самой длинной допустимой (правильно сформированной) подстроки скобок.

Пример:

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

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

1⃣Используем стек для хранения индексов, начальное значение — -1.

2⃣Проходим по строке: если '(', кладем индекс в стек, если ')' — извлекаем элемент.

3⃣Если после извлечения стек пуст — кладем текущий индекс, иначе — обновляем максимум длины как i - stack.top().

😎 Решение:

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stack;
        int m = 0;
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    m = max(m, (i - stack.top()));
                }
            }
        }
        return m;
    }
};

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