Максимальное расстояние между соседними единицами в заданной двоичной строке
Дана двоичная строка 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 — длина двоичной строки.