«1. Обзор

В этом руководстве мы обсудим несколько способов удаления повторяющихся символов из строки в Java.

Для каждой техники мы также кратко расскажем о ее временной и пространственной сложности.

2. Использование Different

Давайте начнем с удаления дубликатов из нашей строки с помощью метода Different, представленного в Java 8.

Ниже мы получаем экземпляр IntStream из заданного строкового объекта. Затем мы используем отдельный метод для удаления дубликатов. Наконец, мы вызываем метод forEach для перебора отдельных символов и добавления их в наш StringBuilder: 

StringBuilder sb = new StringBuilder();
str.chars().distinct().forEach(c -> sb.append((char) c));

Временная сложность: O(n) — время выполнения цикла прямо пропорционально размеру входная строка

Вспомогательный пробел: O(n) — поскольку для внутреннего использования Different использует LinkedHashSet, и мы также сохраняем результирующую строку в объекте StringBuilder

Поддерживает порядок: Да — поскольку LinkedHashSet поддерживает порядок его элементов

И, хотя приятно, что Java 8 так хорошо справляется с этой задачей, давайте сравним это с усилиями по развертыванию нашего собственного.

3. Использование indexOf

Наивный подход к удалению дубликатов из строки просто включает цикл по входу и использование метода indexOf для проверки того, существует ли уже текущий символ в результирующей строке: 

StringBuilder sb = new StringBuilder();
int idx;
for (int i = 0; i < str.length(); i++) {
    char c = str.charAt(i);
    idx = str.indexOf(c, i + 1);
    if (idx == -1) {
        sb.append(c);
    }
}

Время Сложность: O(n * n) — для каждого символа метод indexOf проходит через оставшуюся строку

Вспомогательный пробел: O(n) — требуется линейное пространство, так как мы используем StringBuilder для хранения результат

Поддерживает порядок: Да

Этот метод имеет ту же сложность пространства, что и первый подход, но работает намного медленнее.

4. Использование массива символов

Мы также можем удалить дубликаты из нашей строки, преобразовав ее в массив символов, а затем перебрав каждый символ и сравнив его со всеми последующими символами.

Как видно ниже, мы создаем два цикла for и проверяем, повторяется ли каждый элемент в строке. Если найден дубликат, мы не добавляем его в StringBuilder: 

char[] chars = str.toCharArray();
StringBuilder sb = new StringBuilder();
boolean repeatedChar;
for (int i = 0; i < chars.length; i++) {
    repeatedChar = false;
    for (int j = i + 1; j < chars.length; j++) {
        if (chars[i] == chars[j]) {
            repeatedChar = true;
            break;
        }
    }
    if (!repeatedChar) {
        sb.append(chars[i]);
    }
}

Временная сложность: O(n * n) — у нас есть внутренний и внешний цикл, которые обходят входную строку

Вспомогательный пробел: O(n) — требуется линейный пробел, поскольку переменная chars хранит новую копию введенной строки, и мы также используем StringBuilder для сохранения результата

Поддерживает порядок: Да

Опять же, наша вторая попытка работает плохо по сравнению с предложением Core Java, но давайте посмотрим, к чему мы придем со следующей попыткой.

5. Использование сортировки

В качестве альтернативы повторяющиеся символы можно удалить, отсортировав входную строку, чтобы сгруппировать дубликаты. Для этого нам нужно преобразовать строку в массив символов и отсортировать ее с помощью метода Arrays.sort. Наконец, мы пройдемся по отсортированному массиву символов.

На каждой итерации мы будем сравнивать каждый элемент массива с предыдущим элементом. Если элементы различаются, мы добавим текущий символ в StringBuilder: 

StringBuilder sb = new StringBuilder();
if(!str.isEmpty()) {
    char[] chars = str.toCharArray();
    Arrays.sort(chars);

    sb.append(chars[0]);
    for (int i = 1; i < chars.length; i++) {
        if (chars[i] != chars[i - 1]) {
            sb.append(chars[i]);
        }
    }
}

Временная сложность: O(n log n) — сортировка использует быструю сортировку с двумя опорными точками, которая предлагает O(n log n). ) производительность на многих наборах данных

Вспомогательное пространство: O(n) — так как метод toCharArray делает копию входной строки

Поддерживает порядок: Нет

Давайте попробуем еще раз с нашей последней попыткой.

6. Использование набора

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

В обоих случаях мы будем перебирать входную строку и добавлять каждый символ в набор. Как только символы будут вставлены в набор, мы пройдемся по ним, чтобы добавить их в StringBuilder и вернуть результирующую строку: 

StringBuilder sb = new StringBuilder();
Set<Character> linkedHashSet = new LinkedHashSet<>();

for (int i = 0; i < str.length(); i++) {
    linkedHashSet.add(str.charAt(i));
}

for (Character c : linkedHashSet) {
    sb.append(c);
}

Временная сложность: O(n) — время выполнения цикла прямо пропорционально к размеру входной строки

Вспомогательный пробел: O(n) — место, необходимое для Set, зависит от размера входной строки; также мы используем StringBuilder для хранения результата

«Поддерживает порядок: LinkedHashSet — да, HashSet — нет

И вот мы подошли к подходу Core Java! Не слишком шокирует то, что это очень похоже на то, что уже делает Different.

7. Заключение

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

Как всегда, фрагменты кода можно найти на GitHub.