JuniorКодОчень частоЕщё не отвечали

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

Дана строка. Верните длину наибольшей подстроки без повторяющихся символов.

Требования:

O(n) время — скользящее окно, а не проверка O(n²) каждой подстроки.
Пустая строка возвращает 0; один символ возвращает 1.

int longestUnique(const std::string& s) {
    // ваш код здесь
}

Допишите реализацию.

Двигайте окно с указателем left и таблицей последнего индекса каждого символа. Для каждого right, если символ виден на позиции >= left, сдвиньте left на одну позицию после него. Текущая длина окна — right - left + 1; отслеживайте максимум. Один проход, O(n) время.

✗Сдвигать left на lastSeen+1, даже когда lastSeen до текущего окна, ошибочно его сужая
✗Сбрасывать окно с нуля на повторе, вырождаясь в O(n²)
✗Путать число различных символов с наибольшей подстрокой без дубликатов

→Почему left должен двигаться только вперёд и никогда назад?
→Как вернуть саму подстроку, а не только её длину?

Оглавление

Задача

Найдите длину наибольшей подстроки без повторяющихся символов за O(n) скользящим окном.

Решение

#include <string>
#include <unordered_map>
#include <algorithm>

int longestUnique(const std::string& s) {
    std::unordered_map<char, int> last;          // символ -> последний индекс
    int left = 0, best = 0;
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        auto it = last.find(s[right]);
        if (it != last.end() && it->second >= left)
            left = it->second + 1;               // сдвигаем за дубликат
        last[s[right]] = right;
        best = std::max(best, right - left + 1);
    }
    return best;
}

Ключевые моменты

left сдвигается только если дубликат внутри текущего окна (>= left), иначе он бы поехал назад.
Длина окна — right - left + 1; максимум обновляется на каждом шаге.
O(n): каждый символ обрабатывается один раз.

Открыть тему в роадмапе →

Оглавление

JuniorКодОчень частоЕщё не отвечали

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

Дана строка. Верните длину наибольшей подстроки без повторяющихся символов.

Требования:

O(n) время — скользящее окно, а не проверка O(n²) каждой подстроки.
Пустая строка возвращает 0; один символ возвращает 1.

int longestUnique(const std::string& s) {
    // ваш код здесь
}

Допишите реализацию.

✗Сдвигать left на lastSeen+1, даже когда lastSeen до текущего окна, ошибочно его сужая
✗Сбрасывать окно с нуля на повторе, вырождаясь в O(n²)
✗Путать число различных символов с наибольшей подстрокой без дубликатов

→Почему left должен двигаться только вперёд и никогда назад?
→Как вернуть саму подстроку, а не только её длину?

Оглавление

Задача

Найдите длину наибольшей подстроки без повторяющихся символов за O(n) скользящим окном.

Решение

#include <string>
#include <unordered_map>
#include <algorithm>

int longestUnique(const std::string& s) {
    std::unordered_map<char, int> last;          // символ -> последний индекс
    int left = 0, best = 0;
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        auto it = last.find(s[right]);
        if (it != last.end() && it->second >= left)
            left = it->second + 1;               // сдвигаем за дубликат
        last[s[right]] = right;
        best = std::max(best, right - left + 1);
    }
    return best;
}

Ключевые моменты

left сдвигается только если дубликат внутри текущего окна (>= left), иначе он бы поехал назад.
Длина окна — right - left + 1; максимум обновляется на каждом шаге.
O(n): каждый символ обрабатывается один раз.

Открыть тему в роадмапе →

Оглавление