1. Обзор
В этом уроке сравните способы поиска самой длинной подстроки уникальных букв с помощью Java. Например, самая длинная подстрока уникальных букв в “CODINGISAWESOME” – это “NGISAWE”.
2. Подход Грубой Силы
Давайте начнем с наивного подхода. Для начала, мы можем проверить каждую подстроку, содержит ли она уникальные символы:
String getUniqueCharacterSubstringBruteForce(String input) {
String output = "";
for (int start = 0; start < input.length(); start++) {
Set 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. Оптимизированный Подход
Теперь давайте рассмотрим оптимизированный подход. Мы начинаем пересекать строку слева направо и отслеживать:
- текущая подстрока с неповторяющимися символами с помощью start и end index
- самая длинная неповторяющаяся подстрока вывод
- таблица поиска уже посетил персонажи
String getUniqueCharacterSubstring(String input) {
Map 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 .