Самая длинная подстрока, являющаяся валидной скобочной последовательностью

Сложная
hard , stack
03 July 2024

Описание задачи #

Напишите функцию для поиска самой длинной подстроки, являющейся правильной скобочной последовательностью.

Входные данные: строка s.

Выходные данные: длина самой большой подстроки, являющейся валидной скобочной последовательностью.

Ограничения #

Примеры #

  • Входные данные: s = "(()"

    Ответ: 2

    Пояснения: Самая длинная правильная скобочная последовательность - ()

  • Входные данные: s = ")()())"

    Ответ: 4

    Пояснения: Самая длинная правильная скобочная последовательность - ()()

  • Входные данные: s = ""

    Ответ: 0

Решение через скользящее окно #

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

Для этого нам поможет метод скользящего окна: устанавливаем левую границу на первый элемент, а правую — на длину текущей подстроки. Двигаем окно слева направо, одновременно увеличивая левую и правую границы. Если не будет найдено ни одной подходящей подстроки заданной длины, уменьшаем длину на единицу и снова начинаем проверять все возможные подстроки.

Проверку на валидность можно реализовать с помощью простого счетчика (так как по условиям задачи у нас только один вид скобок) или же с использованием стека.

Реализация #

  • package longest_valid_parentheses

func longestValidParenthesesWindowing(s string) int {
	return recursiveLongestValidParenthesesWindowing(s, len(s))
}

func recursiveLongestValidParenthesesWindowing(s string, substrLen int) int {
	if substrLen == 0 {
		return 0
	}
	left := 0
	right := substrLen
	for right <= len(s) {
		if isValidParenthesesByCounter(s[left:right]) {
			return right - left
		}
		left++
		right++
	}

	return recursiveLongestValidParenthesesWindowing(s, substrLen-1)
}

func isValidParenthesesByCounter(s string) bool {
	counter := 0
	for _, char := range s {
		if char == '(' {
			counter++
			continue
		}

		if counter == 0 {
			return false
		}

		counter--
	}

	return counter == 0
}

  • export function longestValidParenthesesWindowing(s: string): number {
    return recursiveLongestValidParenthesesWindowing(s, s.length)
}

function recursiveLongestValidParenthesesWindowing(s: string, substrLen: number): number {
    if (substrLen === 0) {
        return 0;
    }

    let left = 0
    let right = substrLen

    while (right <= s.length) {
        if (isValidParenthesesByCounter(s.substring(left, right))) {
            return right - left
        }
        left++
        right++
    }

    return recursiveLongestValidParenthesesWindowing(s, substrLen - 1);
}

function isValidParenthesesByCounter(s: string): boolean {
    let counter = 0

    for (const char of s) {
        if (char === '(') {
            counter++
            continue
        }

        if (counter === 0) {
            return false
        }

        counter--
    }

    return counter === 0
}

Оценка сложности #

По времени

Сложность по времени равна O(n^2), поскольку на каждом уровне рекурсии выполняется линейный проход по строке, и таких уровней n.

По памяти

Основным фактором сложности по памяти является рекурсивная глубина. Поскольку на каждом уровне рекурсии используется константное количество дополнительной памяти, общая пространственная сложность функции составляет O(n).

Важно понимать, что это крайне неоптимальный алгоритм. Например, в JS он вызовет ошибку переполнения стека.

Решение через стек #

На самом деле задача решается достаточно легко: максимальная валидная скобочная последовательность — это максимальное расстояние между невалидными подстроками.

То есть, если мы сможем «вырезать» из строки валидные скобочные последовательности, сохранив индексы элементов, то самая большая разница между двумя соседними индексами и будет искомым числом. В этом нам поможет структура данных стек.

Для решения задачи мы будем идти посимвольно по исходной строке:

Исходно в стек помещаем число -1, которое служит для обработки случая, когда вся строка является корректной подстрокой скобок.

Реализация #

  • package longest_valid_parentheses

func longestValidParenthesesStack(s string) int {
	stack := make([]int, 0, len(s))
	stack = append(stack, -1)
	res := 0

	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack = append(stack, i)
			continue
		}

		stack = stack[:len(stack)-1]
		if len(stack) == 0 {
			stack = append(stack, i)
			continue
		}

		res = max(res, i-stack[len(stack)-1])
	}

	return res
}

  • export function longestValidParenthesesStack(s: string): number {
    let stack: number[] = [-1];
    let res = 0;

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
            continue;
        }

        stack.pop();
        if (stack.length === 0) {
            stack.push(i);
            continue;
        }

        res = Math.max(res, i - stack[stack.length - 1]);
    }

    return res;
}

Оценка сложности #

По времени

Для этого решения нам необходимо один раз пройтись по переданной нам строке. То есть сложность по времени — O(n).

По памяти

В этом решении мы выделили дополнительную память на стек. В худшем случае в стек попадут все символы строки, то есть сложность по памяти — O(n).

Оригинал задачи на Leetcode
< Предыдущая задача
Следующая задача >