Longest Substring with At Most Two Distinct Characters
Leetcode #159 | Medium | Скользящее окно | Хэш-таблицы
Идея
Скользящее окно + хэш мапа. Запоминаем частоты символов, если размер мапы больше 2 то двигаем l. Уменьшаем частоты, а если 0 - то удаляем ключ.
Big-O
- Время
O(N) - Память
O(1)
Код
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
Map<Character, Integer> map = new HashMap<>();
int l = 0, res = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
map.put(c, map.getOrDefault(c, 0) + 1);
while (map.size() > 2) {
char lc = s.charAt(l);
map.put(lc, map.get(lc) - 1);
if (map.get(lc) == 0) map.remove(lc);
l++;
}
res = Math.max(res, r - l + 1);
}
return res;
}
}