Поиск максимальной подстроки без повторяющихся символов

Поиск максимальной подстроки без повторяющихся символов

Это классическая задача на применение техники Sliding Window (скользящее окно). Алгоритм позволяет эффективно найти требуемую подстроку за линейное время O(n).

Алгоритм: Sliding Window

Идея очень простая:

1. Используем два указателя: left и right, которые образуют «окно»
2. Расширяем окно, добавляя символы справа
3. Если находим повтор, сужаем окно слева
4. Отслеживаем максимальную длину

Строка: "abcabcbb"

Шаг 1: окно [a] → max = 1
Шаг 2: окно [ab] → max = 2
Шаг 3: окно [abc] → max = 3
Шаг 4: встречаем 'a' (повтор) → удаляем слева [bca]
Шаг 5: окно [bcab] → видим 'b' повторяется → [cab]
Шаг 6: окно [cabc] → видим 'c' повторяется → [abc]
...

Решение с HashSet

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        
        Set<Character> charSet = new HashSet<>();
        int left = 0;
        int maxLength = 0;
        
        // right указатель проходит по всей строке
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            
            // Если символ повторяется, удаляем символы слева
            while (charSet.contains(rightChar)) {
                char leftChar = s.charAt(left);
                charSet.remove(leftChar);
                left++;
            }
            
            // Добавляем текущий символ
            charSet.add(rightChar);
            
            // Обновляем максимальную длину
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
    
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
        System.out.println(lengthOfLongestSubstring("bbbbb")); // 1
        System.out.println(lengthOfLongestSubstring("pwwkew")); // 3
        System.out.println(lengthOfLongestSubstring("")); // 0
        System.out.println(lengthOfLongestSubstring("au")); // 2
        System.out.println(lengthOfLongestSubstring("dvdf")); // 3 ("vdf")
    }
}

Пошаговый пример: "abcabcbb"

┌─────────────────────────────────────────┐
│ Строка: a b c a b c b b                 │
│ Индекс: 0 1 2 3 4 5 6 7                 │
└─────────────────────────────────────────┘

Итерация 1: right=0 ('a')
  charSet = {a}, left = 0
  length = 0 - 0 + 1 = 1, maxLength = 1
  
Итерация 2: right=1 ('b')
  charSet = {a, b}, left = 0
  length = 1 - 0 + 1 = 2, maxLength = 2
  
Итерация 3: right=2 ('c')
  charSet = {a, b, c}, left = 0
  length = 2 - 0 + 1 = 3, maxLength = 3 ✓
  
Итерация 4: right=3 ('a') — повтор!
  while loop:
    - удаляем 'a' (left=0)
    - left = 1
  charSet = {b, c, a}, left = 1
  length = 3 - 1 + 1 = 3, maxLength = 3
  
Итерация 5: right=4 ('b') — повтор!
  while loop:
    - удаляем 'b' (left=1)
    - left = 2
  charSet = {c, a, b}, left = 2
  length = 4 - 2 + 1 = 3, maxLength = 3
  
Итерация 6: right=5 ('c') — повтор!
  while loop:
    - удаляем 'c' (left=2)
    - left = 3
  charSet = {a, b, c}, left = 3
  length = 5 - 3 + 1 = 3, maxLength = 3
  
Итерация 7: right=6 ('b') — повтор!
  while loop:
    - удаляем 'a' (left=3)
    - left = 4
    - 'b' всё ещё в set
    - удаляем 'b' (left=4)
    - left = 5
  charSet = {c, b}, left = 5
  length = 6 - 5 + 1 = 2, maxLength = 3
  
Итерация 8: right=7 ('b') — повтор!
  while loop:
    - удаляем 'c' (left=5)
    - left = 6
  charSet = {b}, left = 6
  length = 7 - 6 + 1 = 2, maxLength = 3

✅ Результат: maxLength = 3

Решение с HashMap (для отслеживания позиций)

Этот вариант немного более эффективен, так как можно сразу переместить left указатель:

public class LongestSubstringOptimized {
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        
        Map<Character, Integer> charIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            
            // Если символ есть в окне, переместим левый указатель
            if (charIndex.containsKey(rightChar)) {
                // Перемещаемся дальше последнего вхождения этого символа
                left = Math.max(left, charIndex.get(rightChar) + 1);
            }
            
            // Сохраняем позицию символа
            charIndex.put(rightChar, right);
            
            // Обновляем максимальную длину
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

Преимущество: Не нужен while loop, а значит несколько быстрее (хотя сложность одинакова).

Анализ сложности

Временная сложность: O(n)

• Каждый символ посещается ровно один раз указателем right
• Каждый символ удаляется максимум один раз
• Общее количество операций: 2n

Пространственная сложность: O(min(n, m))

• n — длина строки
• m — размер алфавита (для ASCII: 128, для Unicode: до 1 млн)
• HashSet/HashMap содержит максимум уникальные символы в текущем окне

Почему Sliding Window работает?

1. Монотонность: Если подстрока [left, right] содержит повтор, то любая подстрока [left, right+k] тоже содержит повтор
2. Оптимальность: Когда мы находим повтор, нет смысла проверять окна с тем же левым указателем
3. Правильность: Мы гарантированно проверяем все возможные окна

Альтернативное решение: Brute Force (неэффективно)

// ❌ O(n²) или O(n³) — медленно
public static int lengthOfLongestSubstringBruteForce(String s) {
    int maxLength = 0;
    
    // Проверяем все подстроки
    for (int i = 0; i < s.length(); i++) {
        Set<Character> charSet = new HashSet<>();
        
        for (int j = i; j < s.length(); j++) {
            if (charSet.contains(s.charAt(j))) {
                break;
            }
            charSet.add(s.charAt(j));
            maxLength = Math.max(maxLength, j - i + 1);
        }
    }
    
    return maxLength;
}

Тестовые случаи

System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
System.out.println(lengthOfLongestSubstring("bbbbb")); // 1 ("b")
System.out.println(lengthOfLongestSubstring("pwwkew")); // 3 ("wke")
System.out.println(lengthOfLongestSubstring("")); // 0
System.out.println(lengthOfLongestSubstring("a")); // 1 ("a")
System.out.println(lengthOfLongestSubstring("au")); // 2 ("au")
System.out.println(lengthOfLongestSubstring("dvdf")); // 3 ("vdf")
System.out.println(lengthOfLongestSubstring("abcdefghijklmnopqrstuvwxyz")); // 26

Рекомендация

Используйте HashMap версию если нужна максимальная производительность, или HashSet версию если нужна простота и читаемость. Обе работают за O(n)!