Longest Substring Without Repeating Characters
Leetcode #3 | Medium | Скользящее окно | Хэш-таблицы
Идея
Скользящее окно с сетом, в начале прохода while двигает l пока есть совпадения, потом максимум из реза и r-l+1, затем добавляем в сет текущий символ
Big-O
- Время
O(N) - Память
O(1)
Код
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int l = 0, res = 0;
for (int r = 0; r < s.length(); r++) {
while (set.contains(s.charAt(r))) { set.remove(s.charAt(l)); l++; }
set.add(s.charAt(r));
res = Math.max(res, r - l + 1);
}
return res;
}
}