«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. the current substring with non-repeating characters with the help of a start and end index
  2. the longest non-repeating substring output
  3. a lookup table of already visited characters
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.