32. Longest Valid Parentheses

leetcode hard

#csharp#hard#leetcode#math#stack#string#tree

Task

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

Пример:

Input: s = "(()"

Output: 2

C# solution

matched/original

public class Solution {
    public boolean IsValid(String s) {
        Stack<char> stack = new Stack<char>();
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                stack.Push('(');
            } else if (stack.Count > 0 && stack.Peek() == '(') {
                stack.Pop();
            } else {
                return false;
            }
        }
        return stack.Count == 0;
    }
    public int LongestValidParentheses(String s) {
        int maxlen = 0;
        for (int i = 0; i < s.Length; i++) {
            for (int j = i + 2; j <= s.Length; j += 2) {
                if (IsValid(s.Substring(i, j - i))) {
                    maxlen = Math.Max(maxlen, j - i);
                }
            }
        }
        return maxlen;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public boolean IsValid(String s) {
        stack<char> stack = new stack<char>();
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                stack.push('(');
            } else if (stack.size() > 0 && stack.Peek() == '(') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.size() == 0;
    }
    public int LongestValidParentheses(String s) {
        int maxlen = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int j = i + 2; j <= s.size(); j += 2) {
                if (IsValid(s.Substring(i, j - i))) {
                    maxlen = max(maxlen, j - i);
                }
            }
        }
        return maxlen;
    }
}

Java solution

matched/original

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push('(');
            } else if (!stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public int longestValidParentheses(String s) {
        int maxlen = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 2; j <= s.length(); j += 2) {
                String substring = s.substring(i, j);
                if (isValid(substring)) {
                    maxlen = Math.max(maxlen, j - i);
                }
            }
        }
        return maxlen;
    }
}

JavaScript solution

matched/original

var longestValidParentheses = function(s) {
    const n = s.length;    const S = [-1];
    let x = 0;    for (let i = 0; i < n; ++i)
        if (s[i] === '(')             S.push(i); // open; mark start index
        else {            S.pop(); // close; remove a start index
            if (!S.length)                 S.push(i); // invalid; reset index to new start
            else                 x = Math.max(x, i - S[S.length - 1]); // valid; save the length
        }    return x;
};

Python solution

matched/original

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

Go solution

matched/original

func isValid(s string) bool {
    stack := []rune{}
    for _, char := range s {
        if char == '(' {
            stack = append(stack, char)
        } else if len(stack) > 0 && stack[len(stack)-1] == '(' {
            stack = stack[:len(stack)-1]
        } else {
            return false
        }
    }
    return len(stack) == 0
}

func longestValidParentheses(s string) int {
    maxlen := 0
    for i := 0; i < len(s); i++ {
        for j := i + 2; j <= len(s); j += 2 {
            if isValid(s[i:j]) {
                if maxlen < j-i {
                    maxlen = j - i
                }
            }
        }
    }
    return maxlen
}

Explanation

Algorithm

1️⃣

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

2️⃣

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

3️⃣

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

😎