round: 4
ticket_no: 07
source_no: 23
slug: remove-invalid-parentheses
topic: DFS / BFS
difficulty: Hard
leetcode_id: 301
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-15
---

# Билет 07 — Remove Invalid Parentheses

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

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

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

Constraints: `1 <= s.length <= 25`; порядок ответов не важен, дубликаты исключить.

## Ответ

> Дословно из `work-07-remove-invalid-parentheses.md`:

```ruby
def remove_invalid_parentheses(s)
  queue = [s]
  visited = Hash.new(0)
  result = []

  while result.empty?
    queue[0..queue.size - 1].each do |variant|
      result.push(variant) if valid?(variant)

      enqueue_new_variants(variant, queue, visited)
    end
  end

  result
end

def valid?(s)
  counter = 0

  s.each_char do |char|
    counter += 1 if char == '('
    counter -= 1 if char == ')'

    return false if counter < 0
  end

  counter == 0
end

def enqueue_new_variants(source, queue, visited)
  (0..source.size - 1).each do |i|
    next unless ['(', ')'].include?(source[i])

    part1 = i > 0 ? source[0..i-1] : ""
    part2 = i < source.size - 1 ? source[i+1..source.size - 1] : ""

    variant = "#{part1}#{part2}"

    unless visited.key?(variant)
      queue.push variant
      visited[variant] = true
    end
  end
end

# run O(n 2^n)
# mem O(2^n)
```

## Разбор

**Что верно:**
- Идея — канонический BFS по уровням удаления: уровень = количество удалённых скобок; на первом же уровне с валидными строками собираем ответ. Это стандарт решения «минимальное число удалений», отлично от идеи раунда 1 (там была DFS-вставка).
- Обработка уровня через снимок `queue[0..queue.size-1]` — корректно: дети добавляются в конец и не мешают текущему уровню.
- `visited` режет дубликаты (одна строка достижима разными путями) — верно и нужно.
- `valid?` с ранним выходом на отрицательном счётчике — правильная проверка ПСП.
- Строки без скобок валидны сразу (`"abc"`), `")(" → [""]`, `"(((((" → [""]` — все тесты 9/9 OK с первого прогона.
- Сложности названы верно: O(n·2ⁿ) (каждая из до 2ⁿ строк проверяется за O(n)) и O(2ⁿ) на visited/очередь.

**Что упущено и ошибки:**
1. ⚠️ `valid?` и `enqueue_new_variants` — глобальные методы; на интервью лучше лямбды внутри функции (самодостаточность ответа).
2. ⚠️ `enqueue_new_variants` вызывается и для валидных вариантов — лишний уровень генерации (не влияет на результат, т.к. цикл завершается).
3. ⚠️ `while result.empty?` — хрупкая форма; чище `until queue.empty?` + возврат при первом уровне с ответами (зависит от факта, что решение всегда есть — оно есть: пустая строка валидна, поэтому зависания нет).
4. ⚠️ Edge cases в ответе не названы: строка без скобок, `"((((("` / `"))))"` (удаляем всё), `")("`, строка из одной буквы, максимальная длина 25, все варианты уже валидные.

**Эталонная идея:**
BFS: очередь уровней (уровень = число удалённых скобок), на каждом уровне генерируем строки с удалением одной скобки, фильтруем валидные (`valid?`: баланс ≥ 0 по пути и 0 в конце). Первый уровень с валидными — ответ целиком; `visited` против дубликатов. Альтернатива: DFS с предвычисленным числом удалений лишних `(`/`)`.

**Время:** O(n·2ⁿ) — генерация до 2ⁿ строк длины n каждая.

**Память:** O(2ⁿ) дополнительная (visited + очередь).

**Граничные случаи:** 1) строка без скобок `"abc"` → сама себе ответ; 2) только открывающие `"((((("` → `[""]`; 3) только закрывающие `"))))"` → `[""]`; 4) `")("` → `[""]`; 5) строка уже валидна `"()"` → не трогаем; 6) дубликаты при генерации — `visited` обязателен; 7) длина 25 — экспонента ограничена constraints.

**Критерии:** идея ✅ · структура данных ✅ · сложность ✅ · граничные случаи ❌ (не названы в ответе)

**Канон сложности:** O(n·2ⁿ) / O(2ⁿ).

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