3. Longest Substring Without Repeating Characters

➡ Задача
3. Longest Substring Without Repeating Characters

➡ Условие

Given a string s, find the length of the longest substring without duplicate characters.

➡ Пример

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

➡ Суть

Наивный способ - перебирать все подстроки O(n²). Это медленно для больших массивов.
Оптимальное решение - использовать Sliding Windows и HashSet

➡ Решение

public int LengthOfLongestSubstring(string s)
{
    if(s.Length <= 1)
        return s.Length;
    
    var left = 0;
    var max = 0;
    
    var dict = new Dictionary<char, int>();
    for (var right = 0; right < s.Length; right++)
    {
        if (dict.TryGetValue(s[right], out var index))
        {
            left = Math.Max(left, index + 1);
        }
        
        dict[s[right]] = right;
        
        max = Math.Max(max, right - left + 1);
    }
    
    return max;
}

➡ HW?
1⃣ Обработка простых случаев
2⃣ Проход по строке с использованием правого указателя. Мы двигаем right (правый указатель), проходя по строке s.
3⃣ Проверка на повтор символа
Если s[right] уже есть в dict, значит символ повторяется. Берем сохраненный индекс index из dict[s[right]. Сдвигаем left, чтобы не было повторов: left = Math.Max(left, index + 1). Это предотвращает сдвиг left назад, если left уже ушел дальше повторного символа.
5⃣ Обновление словаря. Записываем в dict[s[right]] текущий индекс right — теперь этот символ встречается в позиции right.
5⃣ Обновление максимальной длины. Выбираем максимум между max и текущей длиной окна.

#leetcode
#medium
#algorithm
#sliding_window

💡 Channel | ✏ Chat