---
round: 3
ticket_no: 32
source_no: 23
slug: remove-invalid-parentheses
topic: DFS / BFS
difficulty: Hard
leetcode_id: 301
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 32 — Remove Invalid Parentheses

## Условие (как предъявлено)

Дана строка `s`, содержащая скобки и буквы. Удалите минимальное число скобок, чтобы строка стала валидной, и верните все возможные уникальные результаты.

```
Input:  s = "()())()"    →  Output: ["(())()","()()()"]
Input:  s = "(a)())()"   →  Output: ["(a())()","(a)()()"]
Input:  s = ")("         →  Output: [""]
```

Constraints: `1 <= s.length <= 25`.

## Ответ

> Здесь нам нужно написать метод проверки валидности нашей строки в текущий момент. Пишется она с помощью счётчика. Мы проходим строку. Если открывается, мы тогда прибавляем единичку. Если закрывается, вычитаем единичку. Так как у нас только одна скобка бывает одного вида, это означает, что счётчика достаточно. Вот. И если счётчик уходит в отрицательное значение, ну значит проблема, ошибка — невалидная. Так, значит, у нас есть такой метод проверки инвалидности. Вот. Дальше мы, если текущая валидна, мы её сразу возвращаем. Если нет, тогда мы должны сделать вариации наших строк, вот, удалением одной скобки. То есть, мы берём по очереди, удаляем скобочки и отправляем их тоже на проверку рекурсивную. То есть, у нас получается. И смотрим, а здесь нужно использовать очередь. То есть, мы добавляем в очередь эти элементы на проверку, и у нас есть волна проверки. То есть, мы взяли первый элемент. У нас очередь пустая, то есть, там только один элемент мы добавили туда — исходную строку. Проверили её. В рамках проверки у нас добавилось ещё несколько вариаций её, то есть, рангом пониже, то есть, там символов поменьше. При этом важно не добавлять дубликаты, то есть, мы должны ещё использовать список, которые уже добавлены, мы уже как будто пометьте их посещёнными, чтобы не делать лишних обходов. Значит, добавили туда и, собственно, дальше проходим. Выбираем из очереди всё, что там сейчас есть, ну, как индексами. Да, вот, и можем дальше там добавлять. Вот, тоже проверяем на валидность, походу. Вот. Ну и надо учитывать, то у нас здесь могут не только быть скобки, но и другие элементы, они на валидность не влияют.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

**Критерии:** идея ⚠️ · структура данных ⚠️ · сложность ⚠️ · граничные случаи ⚠️

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../algo-solutions/02-extra/02-dfs-bfs/23-remove-invalid-parentheses.md`](../../algo-solutions/02-extra/02-dfs-bfs/23-remove-invalid-parentheses.md)