MiddleКодЧастоЕщё не отвечали
Подсчёт подстрок без повторяющихся символов за O(n)
Дана строка. Посчитайте пары индексов (i, j) с i <= j, для которых подстрока от i до j включительно не содержит повторяющихся символов. Для "abd" ответ — 6.
Требования:
- O(n) по времени, O(размер алфавита) дополнительной памяти.
- Один проход; не перебирайте все подстроки.
long long countDistinctSubstrings(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Скользящее окно: держите left — начало окна без повторов, lastSeen[c] — последний индекс символа. Для каждого правого конца j поставьте left = max(left, lastSeen[c]+1) и прибавьте j - left + 1 (число допустимых левых концов). Один проход, O(n).
- ✗Сдвигать
leftнаlastSeen[c]вместоlastSeen[c]+1, оставляя повтор внутри окна - ✗Не ограничивать через
max(left, ...), из-за чегоleftпрыгает назад на старом повторе - ✗Использовать
intдля итога, когда n достаточно велико для переполнения
- →Чем это отличается от поиска длины самой длинной такой подстроки?
- →Почему
leftдолжен двигаться только вперёд?
Оглавление
Задача
Посчитайте число пар (i, j), i <= j, на которых подстрока не содержит повторов. Для "abd" — 6.
Решение
#include <string>
#include <array>
long long countDistinctSubstrings(const std::string& s) {
std::array<int, 256> lastSeen;
lastSeen.fill(-1);
long long total = 0;
int left = 0;
for (int j = 0; j < static_cast<int>(s.size()); ++j) {
unsigned char c = s[j];
if (lastSeen[c] >= left) left = lastSeen[c] + 1;
total += j - left + 1; // число допустимых левых концов
lastSeen[c] = j;
}
return total;
}Ключевые моменты
- На каждом правом конце добавляем длину текущего окна без повторов.
leftтолько растёт, отсюда O(n).lastSeen[c]+1выкидывает сам повтор из окна.
Оглавление
