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

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

Пример:

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

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

1⃣Используем массив dp, где dp[i] хранит длину самой длинной правильной подстроки, заканчивающейся в i.

2⃣Если s[i] == ')' и перед ней есть (, обновляем dp[i] на основе dp[i-1] и dp[i-dp[i-1]-2].

3⃣Возвращаем максимальное значение из dp.

😎 Решение:

class Solution {
    function longestValidParentheses($s) {
        $s2 = ')'.$s;
        $n = strlen($s2);
        $dp = array_fill(0, $n, 0);

        for ($i = 1; $i < $n; $i++) {
            if ($s2[$i] === ')' && $s2[$i - $dp[$i - 1] - 1] === '(') {
                $dp[$i] = $dp[$i - 1] + $dp[$i - $dp[$i - 1] - 2] + 2;
            }
        }

        return max($dp);
    }
}

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