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

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

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

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

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

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

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

public boolean isUniqueChars2(String str) {
    boolean[] char_set = new boolean[256];
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (char_set[val]) {        //символ уже был найден в строке
            return false;
        }
        char_set[val] = true;
    }
    return true;
}

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

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

public boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        if (checker & (1 << val)) > 0) {
            return false;
        }
        checker |= (1 << val);
    }
    return true;
}

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

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