Detailed explanation
A string is a palindrome when it reads the same forwards and backwards. For example, "madam", "level", and "1221" are palindromes, while "java" is not. In Java, you can check this by comparing a string with its reverse or by comparing matching positions from opposite ends. First clarify the comparison rules: should case, spaces, and punctuation matter? With exact comparison, "Madam" is not a palindrome because uppercase 'M' and lowercase 'm' differ. This clarification matters because preprocessing changes which inputs should pass.
The two-pointer approach is a good default for a beginner interview. Set i to 0 and j to s.length() - 1. While i < j, compare s.charAt(i) with s.charAt(j). Return false immediately if they differ; otherwise, increment i and decrement j. If the loop finishes, return true. Every successful comparison confirms that another pair of outer characters matches. Once the pointers meet or cross, all required pairs have been checked. An odd-length string's middle character does not need comparison because it always matches itself.
A clear implementation is: boolean isPalindrome(String s) { if (s == null) return false; int i = 0, j = s.length() - 1; while (i < j) { if (s.charAt(i) != s.charAt(j)) return false; i++; j--; } return true; }. This version defines null as false; another API could reject null explicitly instead. Empty strings and single-character strings return true because there are no mismatching pairs. The algorithm takes O(n) time in the worst case and O(1) extra space, and a mismatch can terminate it early.
The shorter alternative is s.equals(new StringBuilder(s).reverse().toString()), after handling null. It takes O(n) time and O(n) extra space for the reversed representation. Use equals(), not ==, because you need content comparison rather than reference comparison. Interviewers typically assess your boundary conditions, complexity analysis, and explanation of early termination. For ordinary beginner examples, charAt() is sufficient, but it compares UTF-16 code units. Full Unicode handling may require comparing code points or grapheme clusters instead, depending on what the problem defines as a character.
Key points to remember
- Clarify whether comparison is case-sensitive and whether spaces and punctuation count.
- Compare characters from both ends, moving the pointers inward after each match.
- Return false on the first mismatch; return true when the pointers meet or cross.
- Two pointers use O(n) worst-case time and O(1) extra space.
- Reversing with StringBuilder is concise but uses O(n) extra space.
Common mistakes candidates make
- Using == instead of equals() to compare the original string with its reverse.
- Starting the right pointer at s.length() instead of s.length() - 1.
- Ignoring null handling or silently changing the required case and punctuation rules.
Likely follow-up questions
How would you ignore case, spaces, and punctuation?
For ASCII input, skip non-alphanumeric characters at both pointers and compare the remaining characters after case conversion. This avoids creating a cleaned copy; broader Unicode requirements need a more carefully defined comparison policy.
Why does the loop use i < j rather than i <= j?
When i equals j, both pointers refer to the middle character, which necessarily matches itself. Using i <= j would still work here, but it performs an unnecessary comparison for odd-length strings.
Does charAt() work correctly for every Unicode palindrome?
No, charAt() returns a UTF-16 code unit, and some characters occupy two code units. You can compare code points using s.codePoints().toArray(), but that uses O(n) extra space and still does not treat multi-code-point grapheme clusters as single characters.
Interview tip: State the comparison rules, explain the two-pointer loop using "madam", and finish with complexity and edge cases.