Найдите самую длинную подстроку без повторяющихся символов

1. Обзор

В этом руководстве сравните способы поиска самой длинной подстроки уникальных букв с помощью Java. Например, самая длинная подстрока уникальных букв в «CODINGISAWESOME» — «NGISAWE».

2. Подход грубой силы

Начнем с наивного подхода. Для начала мы можем проверить каждую подстроку на наличие уникальных символов:

String getUniqueCharacterSubstringBruteForce(String input) {
    String output = "";
    for (int start = 0; start < input.length(); start++) {
        Set<Character> visited = new HashSet<>();
        int end = start;
        for (; end < input.length(); end++) {
            char currChar = input.charAt(end);
            if (visited.contains(currChar)) {
                break;
            } else {
                visited.add(currChar);
            }
        }
        if (output.length() < end - start + 1) {
            output = input.substring(start, end);
        }
    }
    return output;
}

Поскольку существует n*(n+1)/2 возможных подстрок, временная сложность этого подхода составляет O(n^2) .

3. Оптимизированный подход

Теперь давайте рассмотрим оптимизированный подход. Мы начинаем обход строки слева направо и отслеживаем:

1. текущая подстрока с неповторяющимися символами с помощью начального и конечного индекса
2. самая длинная неповторяющаяся подстрока на выходе
3. таблица поиска уже посещенных персонажей

String getUniqueCharacterSubstring(String input) {
    Map<Character, Integer> visited = new HashMap<>();
    String output = "";
    for (int start = 0, end = 0; end < input.length(); end++) {
        char currChar = input.charAt(end);
        if (visited.containsKey(currChar)) {
            start = Math.max(visited.get(currChar)+1, start);
        }
        if (output.length() < end - start + 1) {
            output = input.substring(start, end + 1);
        }
        visited.put(currChar, end);
    }
    return output;
}

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

Поскольку мы обходим строку только один раз, временная сложность будет линейной или O(n) .

Этот подход также известен как шаблон скользящего окна .

4. Тестирование

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

@Test
void givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected() {
    assertEquals("", getUniqueCharacterSubstring(""));
    assertEquals("A", getUniqueCharacterSubstring("A"));
    assertEquals("ABCDEF", getUniqueCharacterSubstring("AABCDEF"));
    assertEquals("ABCDEF", getUniqueCharacterSubstring("ABCDEFF"));
    assertEquals("NGISAWE", getUniqueCharacterSubstring("CODINGISAWESOME"));
    assertEquals("be coding", getUniqueCharacterSubstring("always be coding"));
}

Здесь мы пробуем и тестируем граничные условия, а также более типичные варианты использования .

5. Вывод

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

И, как всегда, исходный код доступен на GitHub .