Check Whether a String is a Palindrome - Java

Category: Easy | Concepts used: Two-pointer pointer comparison, String immutability, early exit optimization, requirements gathering

---

Problem Statement

A palindrome reads the same forwards and backwards (case-sensitive by default). Given a string, check if it is a palindrome.

Input : "madam"      Output: true
Input : "hello"       Output: false

Examples (with edge scenarios)

#	Input	Output	Why
1	"madam"	true	Mirror match
2	"hello"	false	"olleh" ≠ "hello"
3	""	true	Empty string is symmetrically balanced (vacuously true)
4	"a"	true	Single character equals itself
5	"A man a plan a canal Panama"	Clarify	Case/space sensitive → false. Case/space insensitive → true. Always clarify this requirement.

⚠️ Common Beginner Mistake

Mistake	Impact	Fix
Reversing the entire string using StringBuilder	Allocates new string copy, wasting (O(N)) memory	Use two pointers pointing inwards to avoid memory allocation
Assuming case-insensitivity by default	Fails for "Madam" due to 'M' != 'm'	Clarify case/space constraints with the interviewer

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm how null and empty strings should behave, whether comparison is case-sensitive, and whether spaces or punctuation count. Java char values are UTF-16 code units, not always complete human-visible Unicode characters, so international text may require code points or grapheme-aware libraries.

Analogy: Folding a Paper Ribbon

Imagine you have a paper ribbon with letters written on it:

• To check if it’s a palindrome, you fold the ribbon exactly in half in the middle.
• You hold it up to a light and compare the letters that overlap on the left and right halves:
  • If the first letter overlaps perfectly with the last, you continue.
  • If any overlapping letters do not match, you throw it away immediately (return false).
  • If you check all overlapping pairs to the fold and they match, it is a palindrome!

---

Solution 1 — Reverse the String and Compare (Naive)

This approach creates a reversed copy of the string to compare.

Intuition

The direct definition of a palindrome is “reads the same forwards and backwards”. Reversing using StringBuilder and checking equality reflects this definition.

public class PalindromeReverse {
    public static boolean isPalindrome(String str) {
        if (str == null) {
            return false;
        }
        String reversed = new StringBuilder(str).reverse().toString();
        return str.equals(reversed);
    }

public static void main(String[] args) {
        System.out.println(isPalindrome("madam")); // true
        System.out.println(isPalindrome("hello"));   // false
        System.out.println(isPalindrome(""));         // true
        System.out.println(isPalindrome("a"));         // true
    }
}

Output:

true
false
true
true

---

Solution 2 — Two-Pointer Comparison (Optimal)

This approach checks symmetry from both ends simultaneously without allocating memory.

Intuition

We place one pointer at the start (left) and one pointer at the end (right). We compare the characters. If they match, we move the pointers inward (left++, right--). If they don’t, we exit early returning false.

public class PalindromeTwoPointer {
    public static boolean isPalindrome(String str) {
        if (str == null) {
            return false;
        }

int left = 0;
        int right = str.length() - 1;

while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false; // Found mismatch -> exit early
            }
            left++;
            right--;
        }
        return true; // All matched
    }

public static void main(String[] args) {
        System.out.println(isPalindrome("madam")); // true
        System.out.println(isPalindrome("hello"));   // false
    }
}

Output:

true
false

Dry Run (str = “madam”)

left = 0 ('m'), right = 4 ('m') -> Match -> left = 1, right = 3
left = 1 ('a'), right = 3 ('a') -> Match -> left = 2, right = 2
left < right (2 < 2 is false) -> Loop terminates.
Result: true

---

📊 Visual Flowchart

graph TD
    Start["Input String S"] --> NullCheck{"S is null?"}
    NullCheck -->|Yes| RetFalse["Return False"]
    NullCheck -->|No| Init["left = 0, right = S.length() - 1"]
    Init --> Loop{"left < right?"}
    Loop -->|Yes| Fetch["cL = S.charAt(left), cR = S.charAt(right)"]
    Fetch --> CheckMatch{"cL == cR?"}
    CheckMatch -->|No| RetFalse
    CheckMatch -->|Yes| IncDec["left++, right--"]
    IncDec --> Loop
    Loop -->|No| RetTrue["Return True"]

---

Interviewer Insights

This is a classic question evaluating optimal spatial complexity and string reference manipulation.

Follow-up questions you might get:

• “What if we need to ignore case, spaces, and punctuation (e.g. ‘A man, a plan, a canal: Panama’) without allocating new strings?” → You can update the two-pointer code to skip non-alphanumeric characters:

  public static boolean isPalindromeAlphanumeric(String str) {
      if (str == null) return false;
      int left = 0, right = str.length() - 1;
      while (left < right) {
          while (left < right && !Character.isLetterOrDigit(str.charAt(left))) {
              left++;
          }
          while (left < right && !Character.isLetterOrDigit(str.charAt(right))) {
              right--;
          }
          char cl = Character.toLowerCase(str.charAt(left));
          char cr = Character.toLowerCase(str.charAt(right));
          if (cl != cr) {
              return false;
          }
          left++;
          right--;
      }
      return true;
  }

  Interview Tip: Explain that doing the character filter inline preserves the (O(1)) space complexity. Pre-filtering the string with .replaceAll("[^a-zA-Z0-9]", "") creates a new string in memory, taking (O(N)) space.

---

Quick Recap

Approach	Space Complexity (Auxiliary)	Time Complexity	Early Exit?	Interview Signal
Reverse & Compare	(O(N))	(O(N))	No	Simple logic, but poor memory footprint
Two-Pointer Check	(O(1))	(O(N))	Yes	Highly optimal, industry standard
In-place Filtered Check	(O(1))	(O(N))	Yes	Advanced, demonstrates deep complexity control