Как посчитать число подстрок без повторяющихся символов?

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

Узнаёте ли вы в задаче скользящее окно и можете ли объяснить, почему к ответу прибавляется именно длина окна. Задачу часто путают с классической «длина самой длинной подстроки без повторов», поэтому следом могут попросить и её, и оценку сложности.

Как отвечать

Сначала уточните, что считаем: все подстроки по позициям или только различные по содержимому. Обычно имеются в виду все по позициям. Для различных понадобится Set<String> или суффиксные структуры, это уже другая задача.

Идея: для каждой правой границы right держим минимальную левую left, при которой окно s[left..right] не содержит повторов. Любая подстрока, которая заканчивается в right и начинается не левее left, тоже без повторов, их ровно right - left + 1. Складываем по всем right.

Реализации две:

• HashSet<Character> и цикл while: при повторе удаляем символы слева, пока дубль не уйдёт. Каждый символ добавляется и удаляется один раз, поэтому в сумме O(n);
• массив последних позиций: int[] last на размер алфавита, заполненный -1. На каждом шаге left = Math.max(left, last[c] + 1), затем last[c] = right. Без коллекций и упаковки char в Character, поэтому обычно быстрее.

Проверьте на примерах вслух: для "bbbbb" ответ 5, для "pwwkew" 12, для "abcabcbb" 18. Сложность O(n) по времени и O(k) по памяти, где k это размер алфавита.

Счётчик держите в long: для длинной строки с большим алфавитом сумма выходит за Integer.MAX_VALUE.

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

Решают другую задачу: возвращают длину максимального окна вместо суммы. Код похож, ответ другой.

В варианте с массивом позиций забывают Math.max и пишут left = last[c] + 1. Если символ встречался левее текущего окна, граница отъезжает назад, и в окно возвращаются повторы.

Не думают о Юникоде: charAt работает с кодовыми единицами UTF-16, и эмодзи из двух char превращается в два «символа». Если строка может содержать такие символы, обходите s.codePoints() и храните позиции в HashMap<Integer, Integer>.