Палиндромы

Сравниваем строку с двух концов

Палиндром читается одинаково слева направо и справа налево. Создавать развёрнутую копию строки для проверки не обязательно: достаточно сравнивать симметричные символы двумя указателями.

static boolean isPalindrome(String text) {
    int left = 0;
    int right = text.length() - 1;

    while (left < right) {
        if (text.charAt(left) != text.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }

    return true;
}

Если хотя бы одна пара различается, ответ уже известен и алгоритм завершается. В худшем случае будет проверена примерно половина пар символов, поэтому время — O(n), а дополнительная память — O(1).

Проверка части строки

Во многих задачах нужно проверить не всю строку, а диапазон между двумя индексами. Тогда полезно сразу передавать его границы в функцию, не создавая отдельную подстроку.

static boolean isPalindrome(String text, int left, int right) {
    while (left < right) {
        if (text.charAt(left++) != text.charAt(right--)) {
            return false;
        }
    }
    return true;
}

Такой вариант удобно повторно использовать внутри более крупных алгоритмов: границы уже определяют нужный фрагмент, а лишний объект String не создаётся.

Условия задачи могут менять правило сравнения

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