Максимальное расстояние между соседними единицами в заданной двоичной строке

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

Дана двоичная строка S , содержащая N символов, задача состоит в том, чтобы найти максимальное расстояние между двумя соседними единицами .

Примеры:

Input: S = “1010010”
Output: 3
Explanation: There are 2 sets of adjacent 1’s in the given index on the indices {0, 2} and {2, 5}. 
The one with the maximum distance among them is {2, 5} with a distance of 3 units.

Input: S = “100000”
Output: -1
Explanation: No set of adjacent 1’s exist in the given string.

Подход : Данная проблема является проблемой реализации. Идея состоит в том, чтобы хранить все индексы единиц в возрастающем порядке в векторе. Следовательно, можно заметить, что требуемый ответ будет максимальной разностью последовательных целых чисел в индексном векторе.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N), где N — длина двоичной строки.

Подход с эффективным использованием пространства: описанный выше подход также может быть реализован без использования дополнительного пространства (вектора). Единственное изменение заключается в достижении максимального расстояния за счет строгого хранения и обновления различий каждый раз, когда мы находим 1 в двоичной строке.

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

Вспомогательное пространство: O(1) , где N — длина двоичной строки.

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