Строки

Почему строки важны в алгоритмах

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

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

Что входит в раздел

• Основы строк. Посмотрим на строки с точки зрения алгоритмов: индексы, обход, неизменяемость и стоимость типичных действий.
• Подсчёт символов. Научимся хранить частоты символов и выбирать между массивом счётчиков и ассоциативной структурой.
• Два указателя. Перенесём знакомую технику на строки и научимся обрабатывать данные с двух сторон без лишних проходов.
• Скользящее окно. Разберём работу с непрерывным фрагментом строки, границы которого двигаются по мере обработки символов.
• Палиндромы. Научимся распознавать строки и диапазоны, которые читаются одинаково с обеих сторон.
• Анаграммы. Посмотрим, как сравнивать строки по составу символов, когда их порядок не важен.
• Задачи на подстроки. Соберём предыдущие приёмы вместе и научимся выбирать подход для задач на непрерывные части строки.

Строка как пространство для алгоритма

String word = "algorithm";

for (int i = 0; i < word.length(); i++) {
    char current = word.charAt(i);
    System.out.println(current);
}

Здесь мы просто идём по строке по индексам. В следующих темах эти же индексы превратятся в границы окна, два указателя или позиции, по которым можно быстро принимать решение о текущем фрагменте.