Алгоритм, определяющий, все ли символы в строке встречаются один раз

При выполнении этого задания нельзя использовать дополнительные структуры данных.

Один из очевидных вариантов решения состоит в том, чтобы сравнить каждый символ строки с любым другим символом строки. Это потребует О(n²) времени и О(1) памяти.

Если изменения строки разрешены, то можно её отсортировать (что потребует О(n log n) времени), а затем последовательно проверить строку на идентичность соседних символов. Будьте осторожны: некоторые алгоритмы сортировки требуют больших объёмов памяти.

Можно слегка оптимизировать задачу — возвращать false, если длина строки превышает количество символов в алфавите. В конце концов, не может существовать строки с 280 уникальными символами, если символов всего 256. Однако если это Unicode-строка, то такая оптимизация не очень поможет.

Наше решение заключается в создании массива логических значений, где флаг с индексом i означает, содержится ли символ алфавита i в строке. Если вы «наткнетесь» на этот же символ во второй раз, можете сразу возвращать false.

Код, реализующий этот алгоритм, представлен ниже:

Оценка времени выполнения этого кода — О(n), где n — длина строки, оценка требуемого пространства — O(1).

Можно уменьшить использование памяти за счёт битового вектора. В следующем коде мы предполагаем, что в строке есть только символы в нижнем регистре a-z. Это позволит нам использовать просто одно значение типа int.

Выбор лучшего решения нужно производить исходя из соответствующих дополнительных ограничений конкретной задачи.

Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).