---
title: Remove Invalid Parentheses
difficulty: Hard
category: BFS / DFS
leetcode_id: 301
revision_count: 1
last_revision: 2026-09-12
---

# Remove Invalid Parentheses

> **LeetCode:** [#301](https://leetcode.com/problems/remove-invalid-parentheses/)
> **Сложность:** Hard
> **Категория:** BFS / DFS

## Условие

Дана строка `s`, содержащая символы `(`, `)` и строчные латинские буквы. Нужно удалить минимальное количество скобок, чтобы строка стала правильной скобочной последовательностью (с учётом букв — они не дёргают баланс). Вернуть **все** возможные варианты.

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

## Ключевая идея

Два подхода, оба годятся на интервью:

**BFS** — удаляем одну скобку за раз, уровень за уровнем. Как только на каком-то уровне (k удалений) появляются валидные строки — возвращаем все, которые на этом уровне нашлись. BFS гарантирует минимальное количество удалений.

**DFS со счётчиками** — одним проходом считаем, сколько `(` и `)` нужно минимально удалить (`rm_open` и `rm_close`), затем DFS-рекурсия перебирает варианты: удалить скобку или оставить, отсекая ветви, где превышен лимит удалений или баланс уходит в минус.

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

- **Время:** O(n × 2^n) — на каждом уровне до C(n, k) строк, каждая проверяется на валидность за O(n). Суммарно O(n·2^n) в худшем случае.
- **Память:** O(2^n) — очередь + visited в худшем случае (все возможные подстроки).
- **DFS-вариант:** O(2^n) время, O(n) память (глубина рекурсии). На практике DFS быстрее за счёт отсечений.

## Решение (Ruby)

### BFS (основной)

```ruby
# @param {String} s
# @return {String[]}
def remove_invalid_parentheses(s)
  queue = [s]
  visited = { s => true }
  result = []
  found = false

  until queue.empty?
    cur = queue.shift

    if balanced?(cur)
      result << cur
      found = true                     # нашли минимальный уровень
    elsif !found                       # не расширяемся, если уровень уже закрыт
      (0...cur.length).each do |i|
        next unless '()'.include?(cur[i])          # режем только скобки
        next if i.positive? && cur[i] == cur[i - 1] # одинаковые подряд — один вариант

        nxt = cur[0...i] + cur[(i + 1)..-1]        # вырезаем i-й символ
        next if visited[nxt]

        visited[nxt] = true
        queue << nxt
      end
    end
  end

  result
end

def balanced?(str)
  open_count = 0
  str.each_char do |c|
    open_count += 1 if c == '('
    open_count -= 1 if c == ')'
    return false if open_count.negative?
  end
  open_count.zero?
end
```

### DFS + precomputed removal counts (бонус)

```ruby
# Дешевле по памяти, быстрее на большом входе (за счёт отсечений)
def remove_invalid_parentheses(s)
  # один проход — считаем, сколько ( и ) нужно удалить
  rm_open = rm_close = 0
  s.each_char do |c|
    if c == '('
      rm_open += 1
    elsif c == ')'
      if rm_open.positive?
        rm_open -= 1
      else
        rm_close += 1
      end
    end
  end

  result = []

  dfs = lambda do |i, open_count, ro, rc, cur|
    if i == s.length
      result << cur if open_count.zero? && ro.zero? && rc.zero?
      return
    end

    c = s[i]

    # ветка 1: удаляем текущую скобку (если ещё есть лимит на этот тип)
    if c == '(' && ro.positive?
      dfs.call(i + 1, open_count, ro - 1, rc, cur)
    end
    if c == ')' && rc.positive?
      dfs.call(i + 1, open_count, ro, rc - 1, cur)
    end

    # ветка 2: оставляем текущий символ
    if c == '('
      dfs.call(i + 1, open_count + 1, ro, rc, cur + c)
    elsif c == ')' && open_count.positive?
      dfs.call(i + 1, open_count - 1, ro, rc, cur + c)
    elsif c != '(' && c != ')'
      dfs.call(i + 1, open_count, ro, rc, cur + c)
    end
  end

  dfs.call(0, 0, rm_open, rm_close, '')
  result.uniq   # разные последовательности удалений могут привести к одной строке
end
```

## Разбор на примере (BFS)

```
s = "()())()", length = 7

Level 0 (0 removals):
  "()())()" → balanced? нет (на 4-м символе balance = -1)

Level 1 (1 removal), candidates (с дедупом по visited):
  удалить (0) → ")())()"       → balance уходит в минус → нет
  удалить )1 → "(())()"       → ✓ валидно!
  удалить (2 → "()))()"       → нет (balance -1)
  удалить )3 → "()()()"       → ✓ валидно!
  удалить )4 → "()()()"       → дубль (skipped by visited)
  удалить (5 → "()()))"       → нет (balance -1)
  удалить )6 → "()())("       → нет (balance не 0)

found = true, все остальные candidates уровня 1 не порождают Level 2

Result: ["(())()", "()()()"]
```

## Edge Cases

- **Пустая строка**: `""` → валидна, возвращаем `[""]`.
- **Только закрывающие/открывающие**: `")))"` → удалить все → `[""]`. `"((("` → `[""]`.
- **Строка уже валидна**: `"(a)()"` → `["(a)()"]` (0 удалений).
- **Строка без скобок**: `"abc"` → `["abc"]` (валидна).
- **Дубликаты из-за одинаковых скобок**: `"(()"` → BFS: `["()"]` (один раз, спасибо visited). `"())(()"` → все уникальны.
- **Максимальная длина**: s.length ≤ 25. BFS экспоненциален, но границы LeetCode проходят. Если бы n было больше — DFS со счётчиками предпочтительнее.

## Типичные ошибки

1. ❌ **Не учесть, что буквы не трогаем** — удалять можно только `(` и `)`.
2. ❌ **Дубликаты в результате** — без visited (BFS) или без uniq/Set (DFS) задача возвращает `["()", "()"]` для `"(()"`.
3. ❌ **BFS без уровня** — без флага `found` код будет продолжать расширяться и вернёт валидные строки не с минимальным числом удалений.
4. ❌ **DFS без учёта open_count > 0 для ')'** — без этой проверки DFS будет закрывать неоткрытые скобки, генерируя невалидные строки (которые потом не пройдут финальную проверку, но ветвление растёт).
5. ❌ **Забыть про `rm_open`/`rm_close` в DFS** — первый проход считает минимальное количество удалений для каждого типа скобок. Без этого DFS не знает, когда остановиться.
6. ❌ **Очередь BFS = Array#shift на больших данных** — `shift` — O(n). Для n ≤ 25 некритично. Ponytail: при больших n заменить на массив с курсором (`idx`).

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| **BFS (уровни)** | **O(n·2^n)** | **O(2^n)** | **Интуитивно понятный, гарантирует минимум удалений** |
| DFS + precomputed counts | O(2^n) | O(n) | Быстрее в среднем, меньше памяти |
| Backtracking с HashSet | O(C(n, k)) | O(n + result) | Похож на DFS, но без предрасчёта счётчиков — больше отсечений |
| Backtracking + BFS (two-way) | O(2^(n/2)) | O(2^(n/2)) | Избыточно для n ≤ 25, но полезно знать |

Для собеседования: начни с BFS — он визуально проще и доказуемо корректен. Если спросят про улучшение по памяти — переходи к DFS со счётчиками.

## Заметки после повторения

_— Заполняется после каждой тренировки._