Определение наибольшей длины подстроки с уникальными символами

Условие

Дана строка str. Требуется вычислить максимальную длину непрерывного фрагмента строки, в котором каждый символ встречается лишь один раз.

Пример 1: Вход: str = "abcabcbb" Выход: 3 Пояснение: Наиболее длинный фрагмент без повторов — "abc", его длина = 3.

Пример 2: Вход: str = "bbbbb" Выход: 1 Пояснение: Наибольший фрагмент без повторов — "b", длина = 1.

Пример 3: Вход: str = "pwwkew" Выход: 3 Пояснение: Наиболее длинный фрагмент без повторов — "wke", длина = 3.

Ограничения: 1 ≤ str.length ≤ 50000

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Реализация
    }
}

Ответ

Поддерживайте скользящее окно без повторов и последние позиции символов. При повторе сдвигайте левую границу за предыдущее вхождение, но никогда не двигайте её назад.

public int lengthOfLongestSubstring(String s) {
    var last = new java.util.HashMap<Character, Integer>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        Integer previous = last.put(s.charAt(right), right);
        if (previous != null) left = Math.max(left, previous + 1);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Время в среднем O(n), память O(k) для разных символов. Здесь длина измеряется в UTF-16 char; для Unicode code points следует сначала выбрать соответствующее представление. Max при обновлении left критичен, например для строки abba.