Самая длинная сбалансированная двоичная подстрока с равным количеством 1 и 0

Опубликовано: 20 Сентября, 2022

Дана двоичная строка str[] размера N . Задача состоит в том, чтобы найти самую длинную сбалансированную подстроку. Подстрока сбалансирована, если она содержит равное количество 0 и 1 .

Примеры:

Input: str = “110101010”
Output: 10101010
Explanation: The formed substring contain equal count of 1 and 0 i.e, count of 1 and 0 is same equal to 4.

Input: str = “0000”
Output: -1

Наивный подход: простое решение — использовать два вложенных цикла для генерации каждой подстроки. И третий цикл для подсчета количества нулей и единиц в текущей подстроке. Затем выведите среди них самую длинную подстроку.
Временная сложность: O(N^3)
Вспомогательное пространство: O(1)

Эффективное решение: с помощью предварительного вычисления сохраните разницу между количеством 0 и 1 с от начала до текущего индекса. Затем эту разницу можно использовать для определения самой длинной подстроки с равными нулями и единицами в качестве самого длинного расстояния между любыми повторяющимися значениями в массиве различий. Используйте хеширование на основе карты для выполнения предварительных вычислений. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте карту <int, int> m[].
  • Установите значение m[0] как -1.
  • Инициализируйте переменные count_0, count_1, res, start и end .
  • Перейдите строку str[] с помощью переменной i и выполните следующие задачи:
    • Отслеживайте количество 1 и 0 как count_1 и count_0 соответственно.
    • Посмотрите, есть ли текущая разница между count_1 и count_0 уже на карте m[] или нет. Если да, то выполните следующие задачи:
      • Подстрока из предыдущего появления и текущего индекса имеет одинаковое количество 0 и 1 .
      • Если текущая длина найденной подстроки больше, чем res , тогда установите найденную подстроку в качестве ответа на данный момент.
    • Если он появляется впервые, сохраните текущую разницу и текущий индекс на карте, т.е. m[count_1 – count_0] равно i .
  • Если count_0 и count_1 оба равны 0, выведите -1.
  • В противном случае выведите подстроку от начала до конца.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ