MiddleКодИногдаЕщё не отвечали

Кратчайшая подстрока, содержащая все буквы заданного алфавита

Дан алфавит (набор требуемых символов) и строка. Найдите кратчайшую подстроку строки, содержащую каждый символ алфавита (лишние символы допустимы), или сообщите, что такой нет.

Требования:

O(n) по длине строки.
Учитывайте окна, заканчивающиеся на самом последнем символе.

// возвращает {start, length} кратчайшего покрывающего окна или {-1, 0}, если нет
std::pair<int,int> minPangram(const std::string& s, const std::string& alphabet) {
    // ваш код здесь
}

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

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

✗Расширять окно, но не сжимать слева для его минимизации
✗Останавливаться рано и пропускать окно, кончающееся на последнем символе
✗Не сообщать неудачу, когда алфавит так и не покрыт полностью

→Как счётчик нехватки позволяет проверять покрытие за O(1) на шаг?
→Как меняется ответ, если лишние символы не допускаются?

Оглавление

Задача

Найдите кратчайшую подстроку, покрывающую все буквы алфавита, за O(n) (или сообщите об отсутствии).

Решение

#include <string>
#include <unordered_map>
#include <utility>

std::pair<int,int> minPangram(const std::string& s, const std::string& alphabet) {
    std::unordered_map<char,int> need;
    for (char c : alphabet) ++need[c];
    int missing = (int)need.size();              // сколько символов ещё не покрыто
    int left = 0, bestStart = -1, bestLen = INT_MAX;
    for (int right = 0; right < (int)s.size(); ++right) {
        if (--need[s[right]] == 0) --missing;    // символ покрыт полностью
        while (missing == 0) {                    // окно покрывает алфавит
            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
            if (++need[s[left]] > 0) ++missing;   // сжимаем слева
            ++left;
        }
    }
    return bestStart < 0 ? std::make_pair(-1, 0) : std::make_pair(bestStart, bestLen);
}

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

Счётчик missing проверяет покрытие за O(1) на шаг.
Окно и расширяется, и сжимается — иначе минимум не найти.
Проход до конца ловит окна, кончающиеся на последнем символе.

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

Оглавление

Кратчайшая подстрока, содержащая все буквы заданного алфавита

Требования:

O(n) по длине строки.
Учитывайте окна, заканчивающиеся на самом последнем символе.

// возвращает {start, length} кратчайшего покрывающего окна или {-1, 0}, если нет
std::pair<int,int> minPangram(const std::string& s, const std::string& alphabet) {
    // ваш код здесь
}

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

Решение

#include <string> #include <unordered_map> #include <utility> std::pair<int,int> minPangram(const std::string& s, const std::string& alphabet) { std::unordered_map<char,int> need; for (char c : alphabet) ++need[c]; int missing = (int)need.size(); // сколько символов ещё не покрыто int left = 0, bestStart = -1, bestLen = INT_MAX; for (int right = 0; right < (int)s.size(); ++right) { if (--need[s[right]] == 0) --missing; // символ покрыт полностью while (missing == 0) { // окно покрывает алфавит if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; } if (++need[s[left]] > 0) ++missing; // сжимаем слева ++left; } } return bestStart < 0 ? std::make_pair(-1, 0) : std::make_pair(bestStart, bestLen); }