☕ DSA Java Articles

Topics › Basics › Learn Basic Recursion

Check if String is Palindrome or Not

Easy TUF ID 378 A2Z

Java source ↗ Edit this article ↗

Problem

Given a string s, return true if it is a palindrome, i.e. it reads the same from left to right and from right to left, and false otherwise. The comparison is exact: case matters and every character counts.

The problem appears on the recursion sheet because it is the natural follow-up to reversing an array: the same single-index recursion works, with the swap replaced by a comparison, and it introduces early termination in a recursive function (one mismatch decides the whole answer).

A popular variant (LeetCode 125, “Valid Palindrome”) ignores everything that is not a letter or digit and compares case-insensitively. We cover it at the end; the recursion is identical once the string is cleaned.

Constraints: 0 ≤ |s| ≤ 10^5, lowercase letters in the basic version.

Example 1

s = "hannah"
answer = true             // h-a-n-n-a-h reads the same backwards

Example 2

s = "abca"
answer = false            // the ends match (a, a) but b != c in the middle

Example 3

s = ""
answer = true             // the empty string trivially reads the same both ways

Approach 1: Brute force, reverse and compare

Intuition. The definition literally says “equals its own reverse”, so build the reversed string and compare. It is correct and short, but it allocates a full copy of the string even when the first and last characters already differ.

Algorithm.

  1. Build reversed from s (here with StringBuilder.reverse()).
  2. Return s.equals(reversed).
static boolean bruteForce(String s) {
    String reversed = new StringBuilder(s).reverse().toString();
    return s.equals(reversed);
}

Complexity. Time O(n) to reverse plus O(n) to compare. Space O(n) for the reversed copy.

Approach 2: Two pointers, iterative

Intuition. A string is a palindrome exactly when s[0] == s[n-1], s[1] == s[n-2], and so on until the pointers meet. So walk l from the left and r from the right and compare the pair at every step. The moment a pair differs we can stop with false; if the pointers cross without a mismatch, every pair matched and the answer is true. No extra memory is needed.

Algorithm.

  1. Set l = 0, r = n - 1.
  2. While l < r: if s[l] != s[r], return false; otherwise l++, r--.
  3. Return true.
static boolean iterative(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) return false;
        l++;
        r--;
    }
    return true;
}

Complexity. Time O(n) in the worst case (a real palindrome needs n / 2 comparisons), often much less because of early exit. Space O(1).

Approach 3: Recursive, single index

Intuition. Turn the loop into a recursive function with one parameter i. The call isPalindromeFrom(s, i) answers “do all pairs from position i inward match?”. The partner of i is n - 1 - i, so there is no need for a second parameter. There are three cases:

This is functional recursion where the combination step is trivial (the result of the inner call is the result), which is why the recursive call sits in tail position.

Algorithm.

  1. Start with isPalindromeFrom(s, 0).
  2. If i >= n / 2, return true.
  3. If s.charAt(i) != s.charAt(n - 1 - i), return false.
  4. Return isPalindromeFrom(s, i + 1).
static boolean recursive(String s) {
    return isPalindromeFrom(s, 0);
}

private static boolean isPalindromeFrom(String s, int i) {
    int n = s.length();
    if (i >= n / 2) return true;                        // base case: reached the middle without a mismatch
    if (s.charAt(i) != s.charAt(n - 1 - i)) return false;
    return isPalindromeFrom(s, i + 1);                  // the outer pair matches, check the rest
}

Dry run on s = "abca" (n = 4, so the middle is n / 2 = 2):

call s[i] s[n-1-i] decision
isPalindromeFrom(s, 0) a a match, recurse
isPalindromeFrom(s, 1) b c mismatch, return false

The false propagates straight back through the first call, and the third pair is never looked at.

Complexity. Time O(n): at most n / 2 + 1 calls. Space O(n) for the call stack, more precisely n / 2 + 1 frames in the worst case.

Variant: ignore non-alphanumerics and case (LeetCode 125)

Intuition. Sentences such as "A man, a plan, a canal: Panama" are palindromes only after dropping spaces and punctuation and folding case. The cleanest way to handle that is to normalise first: build a new string with only the letters and digits, lower-cased, and then run exactly the same recursion on it. Separating “what counts as a character” from “is it symmetric” keeps both parts simple.

static boolean recursiveAlphanumeric(String s) {
    StringBuilder clean = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isLetterOrDigit(c)) clean.append(Character.toLowerCase(c));
    }
    return isPalindromeFrom(clean.toString(), 0);
}

For "race a car" the cleaned string is "raceacar", which is not a palindrome (e versus a at the second pair), so the answer is false. A string made only of separators, such as " ", cleans to the empty string and is a palindrome.

Complexity. Time O(n), space O(n) for the cleaned copy. (It can be done in O(1) space by skipping non-alphanumerics inside the two-pointer loop, at the price of messier code.)

Edge cases and pitfalls