Алгоритми та структури даних · Middle · Запитання 18 з 75
Найдовший підрядок без повторюваних символів: яка ідея за O(n)?
- 1Згенерувати всі підрядки й перевірити кожен на дублікати
- ✓Правильна відповідь: При повторі зсунути ліву межу вікна за попередню позицію символу
- 3Відсортувати символи й порахувати найдовшу серію
Пояснення
Зберігайте останній індекс кожного символу в map. Якщо поточний символ уже траплявся всередині вікна, перенесіть ліву межу на last + 1. Кожен індекс рухається лише вперед, тож загальна робота O(n).