Как считать количество подстрок при сдвиге левого и правого указателей

Что проверяют

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

Как отвечать

Объясните инвариант. Окно [left, right] удовлетворяет условию, и условие монотонно: если окно подходит, подходит и любое его подокно. Тогда все подстроки, которые заканчиваются на right и начинаются в left, left+1 и дальше до right, тоже подходят, и их ровно right-left+1. Каждая подстрока считается один раз, по своему правому концу.

Схема для условия «не больше K различных символов»:

• расширение: сдвигаете right, увеличиваете счётчик символа в int[] freq, при переходе с 0 на 1 растёт число различных;
• сжатие: пока различных больше K, уменьшаете счётчик символа на позиции left и сдвигаете left;
• подсчёт: после сжатия count += right-left+1;
• сложность: каждый указатель проходит строку один раз, итого O(n) по времени и O(размер алфавита) по памяти.

Для «ровно K» берите разность atMost(K)-atMost(K-1). Для условий вида «содержит хотя бы…» логика обратная: когда окно подошло, подходят и все его продолжения вправо, поэтому после сжатия к ответу прибавляют текущий left.

Для латиницы или ASCII массив int[128] быстрее HashMap<Character, Integer>: нет упаковки в Character и Integer и нет хеширования.

Где спотыкаются

Применяют приём к немонотонному условию. «Сумма подмассива равна K» при отрицательных числах двумя указателями не решается, там нужны префиксные суммы с HashMap.

Хранят ответ в int. Для строки длиной 100 000 подстрок около пяти миллиардов, это больше Integer.MAX_VALUE, нужен long.

Прибавляют единицу за каждое валидное окно или перебирают left заново на каждом шаге. В первом случае ответ неверный, во втором получается O(n²) и смысл двух указателей пропадает.