Ctrl K

Обменами к правильным скобкам

Средняя
Дана строка brackets чётной длины n, в которой ровно n / 2 открывающих скобок [ и ровно n / 2 закрывающих ]. Скобочная последовательность правильная, если каждой открывающей скобке можно сопоставить закрывающую правее неё так, чтобы пары не пересекались, — как в [[]] или [][], но не в ][ или []][. За один ход можно поменять местами любые два символа строки. Верните наименьшее число ходов, которое сделает brackets правильной.
Пример 1
brackets="]][[" → 1

Меняем местами символы с индексами 0 и 3: получается [][].

Пример 2
brackets="[][]" → 0

Строка уже правильная.

Пример 3
brackets="]]]][[[[" → 2

Обмен индексов 0 и 7 даёт []]][[[], затем обмен индексов 2 и 5 — [][][][]. Одним обменом не обойтись.

Ограничения
  • 2 ≤ len(brackets) ≤ 10⁶, длина чётная
  • brackets состоит только из [ и ]
  • Открывающих и закрывающих скобок поровну
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКаждая буква по разу СредняяВычеркнуть цифры ради минимума СредняяНаименьшая последовательность по стрелкам СредняяПерестроить середину шеренги СредняяСкобки со звёздочками Средняя
загружаем Python…
Вход
brackets="]][["
Ожидается
1

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 34 теста на сервере, включая скрытые.