Задачи на подстроки

Подстрока — это непрерывный диапазон

Подстрока состоит из символов, идущих подряд. Это главное свойство, которое определяет выбор алгоритма: её удобно описывать двумя границами left и right, а затем двигать их вместо перебора всех возможных пар границ.

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

Пример: самый длинный фрагмент без повторов

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

Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0;
int best = 0;

for (int right = 0; right < text.length(); right++) {
    char c = text.charAt(right);

    if (lastSeen.containsKey(c)) {
        left = Math.max(left, lastSeen.get(c) + 1);
    }

    lastSeen.put(c, right);
    best = Math.max(best, right - left + 1);
}

Выражение с Math.max принципиально важно: левая граница не должна возвращаться назад из-за старого появления символа, которое уже осталось за текущим окном. Каждый right проходит строку один раз, а left только движется вперёд, поэтому при среднем O(1) доступе к HashMap решение работает за O(n).

Не создавай подстроку без необходимости

Во время поиска обычно достаточно хранить границы и длину лучшего диапазона. Если задача требует вернуть сам текст, можно запомнить bestStart и создать substring один раз после завершения алгоритма. Так код не создаёт промежуточные строки на каждой итерации.