Какие свойства подстрок помогают их классифицировать и избегать пересечений?

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

Формулировка размыта намеренно: интервьюер смотрит, сумеете ли вы свести её к формальной модели. Подстрока здесь это интервал индексов, а классификация означает выбор признака, по которому подстроки сравнивают или группируют. Следом обычно дают задачу: разбить строку на максимальное число частей так, чтобы каждая буква встречалась только в одной.

Как отвечать

Назовите свойства, на которых строятся такие решения:

• границы: подстрока задаётся полуинтервалом [start, end), как в String.substring. Два интервала пересекаются, если a.start < b.end && b.start < a.end. Максимум непересекающихся даёт жадный выбор по правому концу, как в задаче о расписании;
• первое и последнее вхождение символа: один проход, массив int[26] для латиницы или Map<Character, Integer> в общем случае. Для разбиения на части расширяете правую границу до последнего вхождения каждой встреченной буквы и режете, когда текущий индекс её достиг;
• замкнутость: подстрока содержит все вхождения каждого своего символа. Кандидатов строят от первого вхождения каждой буквы, их не больше размера алфавита, дальше снова жадный выбор;
• канонический вид: для группировки анаграмм ключом служит отсортированная строка или вектор частот символов;
• хэш: полиномиальный rolling hash Рабина-Карпа после предподсчёта за O(n) сравнивает любые две подстроки за O(1). Коллизии возможны, поэтому совпадение перепроверяют или берут два модуля;
• префикс-функция: из алгоритма КМП, находит все вхождения образца, включая накладывающиеся. Для непересекающихся после совпадения сдвигаетесь на длину образца.

Проговорите сложность: разбиение по последним вхождениям занимает O(n) времени и O(1) памяти при фиксированном алфавите.

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

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

Путают повторяющиеся подстроки с пересекающимися. Повтор касается содержимого, пересечение касается индексов.

Приписывают суффиксному дереву логарифмический поиск. Поиск образца в нём линеен по длине образца и не зависит от длины текста.