Для решения данной задачи можно использовать алгоритм двух указателей (sliding window). Идея заключается в создании окна, которое будет представлять собой текущий подстроку без повтора символов. Мы будем продвигать правый указатель по строке и добавлять новые символы в наше окно, пока не найдем повторяющийся символ. Когда мы обнаруживаем повторяющийся символ, мы продвигаем левый указатель до тех пор, пока удаляем все повторяющиеся символы из нашего окна.
Вот как это может быть реализовано на Java:
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>(); // множество для хранения уникальных символов
int left = 0; // левый указатель
int right = 0; // правый указатель
int maxLen = 0; // длина максимальной подстроки без повтора символов
while (right < s.length()) {
// пока правый указатель не достиг конца строки
// если символ не повторяется, добавляем его в множество и расширяем окно
if (!set.contains(s.charAt(right))) {
set.add(s.charAt(right));
right++;
maxLen = Math.max(maxLen, set.size());
// обновляем максимальную длину подстроки при необходимости }
else { // если символ уже есть в множестве, сужаем окно set.remove(s.charAt(left));
left++;
}
}
return maxLen;
}
Здесь мы используем множество для хранения уникальных символов в текущей подстроке. При каждом шаге мы будем проверять, содержит ли множество новый символ. Если да, то мы его добавляем и расширяем наше окно. Если нет, мы сужаем окно, удаляя символы слева до тех пор, пока не уберем дубликат.
Алгоритм работает за время O(n), где n - длина строки s.
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov