Корневая на строках
Данные идеи очень полезны в задачах, где есть ограничение на суммарный размер строк. Обозначим это ограничение за $\sum |S|$.
Разбиение на длинные и короткие строки
Назовем строку $S \textit{длинной}$, если $|S| \ge \sqrt{\sum |S|}$. Все оставшиеся строки назовем $\textit{короткими}$.
Утверждение:
Существует не более $\sqrt{\sum |S|}$ длинных строк.
Доказательство:
Пусть существует более $\sqrt{\sum | S | }$ длинных строк. Тогда их суммарная длина больше, чем $\sqrt{\sum | S | } \cdot \sqrt{\sum | S | } = \sum | S | $, чего не может быть.
Количество разных длин
Утверждение:
Количество различных длин строк не более, чем $O(\sqrt{\sum |S|})$.
Доказательство:
Пусть количество различных длин равно $x$. Тогда минимальная возможная сумма длин~--- это сумма чисел от 1 до $x$. $$\sum_{i=1}^x i = \frac{x(x + 1)}{2}$$ Так как это число должно быть меньше, чем $\sum |S|$, то $x = O(\sqrt{\sum |S|})$