# Билет 07 — рабочий лист

## Условие

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

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

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

## Решение — пиши здесь

```ruby
#
# Твоя реализация. Не забудь: проговаривай (пиши в комментариях) —
# 1) идею, 2) сложность по времени, 3) сложность по памяти,
# 4) граничные случаи.
#

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)