Все ли символы в строке встречаются только один раз?
Реализовать алгоритм, определяющий все ли символы в строке встречаются только один раз. Если при этом запрещено использовать дополнительные структуры данных?
Прежде всего, стоит уточнить о какой кодировке идет речь: обычной ASCII или Юникоде? От этого будет зависеть размер памяти, который потребуется для решения, но сама логика решения останется неизменной.
Одно из возможных решений — создать массив логических значений, где флаг с индексом i указывает, присутствует ли символ алфавита с этим индексом в строке. При повторном обнаружении этого символа можно сразу возвращать false . Также можно сразу вернуть false если длина строки превышает количество символов в алфавите.
Алгоритм имеет сложность по времени O(n) , где n — длина строки и по памяти O(1) . В принципе, можно считать, что и по времени сложность равна O(1) т.к. длина строки не может быть больше 128 .
А если при этом запрещено использовать дополнительные структуры данных, такие как битовый массив set ?
Если предположить, что количество букв в алфавите не превосходит 32, например, заранее известно, что используются только буквы a-z в нижнем регистре (26 штук), то можно переписать решение выше без использования массива — с использованием одного числа и побитовых операций.
Сперва решение может показаться немного неясным, но на самом деле логика ровно такая же, только вместо явного массива бит используется number, который является 32-битным вектором (JavaScript хранит числа в 32 битах).
На каждом шаге цикла «взводится» бит, который соответствует определенному символу в строке и проверяет, что на каждой следующей позиции ноль, т.е. раньше этот бит не был выставлен в единицу.
Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.
