2743. Count Substrings Without Repeating Character — разбор задачи

1. Условие задачи

Дано: строка s, состоящая из строчных английских букв.

Нужно: посчитать количество её подстрок, в которых все символы различны.

Подстрока должна быть непрерывной. Например, ab — подстрока строки abc, а ac — уже нет.

Одинаковые по содержанию подстроки, стоящие на разных позициях, считаются отдельно. Поэтому в строке abab подстрока ab встречается дважды и даёт два элемента в ответе.

Пример: s = "abab" → 7.

длина 1: a, b, a, b — 4 подстроки;
длина 2: ab, ba, ab — 3 подстроки;
подстроки длины 3 и 4 содержат повторы.

Итого получаем 4 + 3 = 7.

Ограничения:

1 <= len(s) <= 10^5;
строка содержит только строчные английские буквы.

2. Решение

Решение в лоб

Можно перебрать все пары границ подстроки, а затем для каждой подстроки отдельно проверить уникальность символов с помощью множества.

Подстрок всего O(N²), а одна проверка может занять O(N). В худшем случае получаем O(N³), что слишком медленно для строки длины до 10^5.

Даже если для каждой левой границы расширять подстроку вправо и останавливать расширение на первом повторе, мы всё равно заново проделаем похожую работу для соседних начал. Нужен способ переиспользовать уже найденное окно без повторов.

Главная идея: считаем подстроки по правой границе

Будем поддерживать окно s[left:right + 1], в котором все символы различны.

В словаре last_seen будем хранить последнюю позицию каждого символа. Когда добавляем новый символ s[right], возможны два случая:

символ ещё не встречался внутри окна — границу left менять не нужно;
символ уже встречался внутри окна — сразу переносим left на позицию после прошлого вхождения.

После этого окно снова содержит только уникальные символы.

Теперь ключевой вопрос: сколько подходящих подстрок заканчивается в позиции right?

Это все суффиксы текущего окна:

s[left:right + 1]
s[left + 1:right + 1]
...
s[right:right + 1]

Их ровно right - left + 1, то есть длина окна. Все они корректны: если в целом окне нет повторов, то и в любом его суффиксе повторов быть не может.

Именно поэтому на каждом шаге мы прибавляем к ответу длину текущего окна.

Главный инсайт задачи

Когда мы добавляем новый символ справа и восстанавливаем окно без повторов, число новых корректных подстрок равно длине этого окна.

Почему? Все новые подстроки обязаны заканчиваться на только что добавленном символе. Это ровно все суффиксы текущего окна, а суффиксов у строки столько же, сколько в ней символов.

Например, после добавления c окно стало равно abc. Появились три новые подстроки: c, bc и abc. Длина окна равна 3, и новых подстрок тоже 3.

Это работает и при повторе. Если к окну abc добавить a, после переноса левой границы останется корректное окно bca. Новые подстроки: a, ca и bca — снова ровно 3, то есть right - left + 1.

Алгоритм по шагам

Создаём пустой словарь last_seen и ставим left = 0.
Двигаем правую границу right по строке.
Если s[right] уже встречался внутри текущего окна, переносим left на позицию после прошлого вхождения.
Записываем right как последнюю позицию текущего символа.
Прибавляем к ответу right - left + 1.
После обработки всей строки возвращаем накопленную сумму.

Обрати внимание на выражение max(left, last_seen[char] + 1). Предыдущее вхождение символа может находиться уже левее текущего окна. В таком случае двигать left назад нельзя.

Визуализация на `s = "abab"`

right	Новый символ	left до проверки	left после обновления	Корректное окно	Новых подстрок	Всего
0	`a`	0	0	`a`	1	1
1	`b`	0	0	`ab`	2	3
2	`a`	0	1	`ba`	2	5
3	`b`	1	2	`ab`	2	7

Например, при right = 2 левая граница прыгает с 0 на 1, и остаётся окно ba. Оно даёт две новые подстроки, заканчивающиеся в позиции 2: ba и a.

Код на Python: решение со словарём

Этот короткий вариант встречается среди популярных пользовательских решений.

class Solution:
    def numberOfSpecialSubstrings(self, s: str) -> int:
        last_seen = {}
        left = 0
        answer = 0

        for right, char in enumerate(s):
            if char in last_seen:
                # Граница никогда не должна двигаться назад
                left = max(left, last_seen[char] + 1)

            last_seen[char] = right
            # Все суффиксы корректного окна тоже корректны
            answer += right - left + 1

        return answer

Почему алгоритм работает

Перед обработкой очередного символа окно не содержит повторов. После добавления s[right] единственным возможным повтором становится именно этот новый символ.

Если прошлое вхождение нового символа находится внутри окна, мы переносим left сразу за него. Если оно находится левее окна, max оставляет границу на месте. Значит, после обновления границы инвариант восстановлен: все символы окна различны.

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

Следовательно, алгоритм учитывает ровно right - left + 1 подходящих подстрок для каждой правой границы, не пропускает ни одну из них и не считает ни одной лишней.

Продвинутое решение: без словаря

Представим, что на собеседовании попросили решить задачу без словаря. По условию строка состоит только из 26 строчных английских букв, поэтому частоты можно хранить в массиве freq фиксированного размера.

При добавлении символа увеличиваем его частоту. Если она стала больше единицы, двигаем левую границу по одному шагу и уменьшаем частоты уходящих символов, пока повтор не исчезнет.

Это решение совпадает с подходом из официального Editorial.

class Solution:
    def numberOfSpecialSubstrings(self, s: str) -> int:
        freq = [0] * 26
        left = 0
        answer = 0

        for right, char in enumerate(s):
            char_index = ord(char) - ord("a")
            freq[char_index] += 1

            # Убираем повтор нового символа из окна
            while freq[char_index] > 1:
                left_index = ord(s[left]) - ord("a")
                freq[left_index] -= 1
                left += 1

            answer += right - left + 1

        return answer

Проверять нужно только частоту нового символа. До его добавления окно уже было корректным, поэтому никакой другой символ внезапно стать повторяющимся не мог.

Оба решения работают за линейное время. Вариант со словарём проще: он сразу переставляет левую границу в нужное место. Вариант с freq полезно показать как более низкоуровневое решение без словаря.

Краевые случаи

Один символ. Единственная подстрока подходит, ответ равен 1.
Все символы одинаковые. Например, для ooo окно после каждого сжатия имеет длину 1, поэтому ответ равен 3.
Все символы различны. Окно никогда не сжимается, и ответ равен 1 + 2 + ... + N = N(N + 1) / 2.
Повтор находится вне текущего окна. В решении со словарём выражение max(left, last_seen[char] + 1) не позволяет сдвинуть левую границу назад.
Пересекающиеся подстроки. Они учитываются отдельно, потому что мы считаем все допустимые начала для каждой правой границы.

3. Сложность алгоритма

Решение со словарём

Для каждого символа выполняется константное количество операций со словарём.

Итог по времени: O(N).

В словаре хранится не больше 26 символов.

Итог по дополнительной памяти: O(1).

Решение без словаря с массивом частот

Правая граница проходит по строке один раз.
Левая граница тоже только движется вперёд и проходит не больше N позиций.
Каждый символ добавляется в окно один раз и удаляется из него не более одного раза.

Итог по времени: O(N).

Массив частот всегда содержит 26 элементов.

Итог по дополнительной памяти: O(1).

Вариация от Яндекса

В Яндексе эту задачу формулируют через индексы:

Дана строка символов. Нужно найти количество пар индексов i и j, где i <= j, таких, что в подстроке от i до j включительно нет повторяющихся символов.

Например, для строки aba ответ равен 5:

[0, 0] → "a"
[0, 1] → "ab"
[1, 1] → "b"
[1, 2] → "ba"
[2, 2] → "a"

По сути, формулировка не меняет задачу. Каждая пара [i, j] задаёт одну подстроку: i — индекс её начала, а j — индекс конца.

Зафиксируем правую границу j = right. После обновления окна все допустимые индексы начала лежат в диапазоне:

left, left + 1, ..., right

Их количество равно right - left + 1. Это ровно та величина, которую мы прибавляем к ответу в основном решении. Поэтому для формулировки Яндекса алгоритм и код вообще не меняются: LeetCode просит посчитать особые подстроки, а Яндекс — соответствующие им пары границ.

Для s = "aba" алгоритм работает так:

right	Символ	left	Подходящие начала `i`	Новых пар	Всего
0	`a`	0	`0`	1	1
1	`b`	0	`0, 1`	2	3
2	`a`	1	`1, 2`	2	5

Вывод

Главный паттерн задачи: если текущее окно удовлетворяет условию, то можно посчитать сразу все его допустимые суффиксы. Для правой границы right их количество равно длине окна right - left + 1.

Это превращает перебор огромного числа подстрок в один линейный проход. Сначала эту идею проще реализовать через словарь последних позиций. Если словарь использовать нельзя, тот же инвариант поддерживается массивом частот и сжатием окна во внутреннем цикле.

🐆