Definition
- Palindrome – a string that reads the same forwards and backwards, such as
"madam"or"racecar". - Two-pointer technique – place
leftat index 0 andrightat the last index, compare the characters, and move both pointers inward until they meet. - Early exit – return
falsethe moment any mirrored pair does not match, avoiding unnecessary work. - Complexity – O(n) time for the single pass and O(1) extra space because only two index variables are needed.
- Normalisation – lowercase and strip non-alphanumeric characters before scanning to handle case-insensitive or punctuation-tolerant checks.
National Bank of India lets customers choose a short memorable reference code, and the system flags codes that read the same both ways as symmetric. A clerk checks a code by comparing the first and last letters, then the second and second-last, moving toward the middle. If every pair matches, the code is a palindrome.
Understanding the Concepts
What is a palindrome?
A palindrome is a string that reads the same from left to right as it does from right to left. Simple examples include "madam", "level", and "racecar". A single character is trivially a palindrome, and an empty string is also considered a palindrome because there is nothing to contradict the definition.
In the banking domain, Rajesh at National Bank of India generates reference codes for transactions. Some codes like "ABCBA" happen to be palindromes, and the system marks them as symmetric for a quick visual check during reconciliation.
package com.bank.core;
public class PalindromeBasics {
public static boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
System.out.println(isPalindrome("madam")); // true
System.out.println(isPalindrome("bank")); // false
System.out.println(isPalindrome("ABCBA")); // true
}
}
true
false
true
How does the two-pointer technique work?
The two-pointer technique places left at index 0 and right at the last index. At each step, you compare the characters at left and right. If they differ, the string is not a palindrome and you return false immediately. If they match, you move left forward and right backward. The loop continues while left < right. When the pointers meet or cross, every pair has matched and the string is a palindrome.
The key insight is that a palindrome is defined by mirrored pairs. You only need to check up to the middle of the string because the second half mirrors the first half.
package com.bank.core;
public class TwoPointerPalindrome {
public static boolean isPalindrome(String s) {
char[] chars = s.toCharArray();
int left = 0;
int right = chars.length - 1;
while (left < right) {
if (chars[left] != chars[right]) {
return false; // early exit on first mismatch
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
String refCode = "SAV12321VAS";
System.out.println(refCode + " is palindrome: " + isPalindrome(refCode));
}
}
SAV12321VAS is palindrome: true
How is the two-pointer method different from reverse-and-compare?
The reverse-and-compare method creates a reversed copy of the string and checks if it equals the original. The two-pointer method checks characters in place without creating any new string.
| Feature | Two-pointer | Reverse-and-compare |
|---|---|---|
| Time complexity | O(n) | O(n) |
| Space complexity | O(1) | O(n) for the reversed string |
| Early exit | Yes, on first mismatch | No, must reverse the entire string first |
| Clarity | Slightly more code | Very concise with StringBuilder |
package com.bank.core;
public class PalindromeComparison {
// Method 1: Two pointers (O(1) space, early exit)
public static boolean twoPointer(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
// Method 2: Reverse and compare (O(n) space, no early exit)
public static boolean reverseCompare(String s) {
String reversed = new StringBuilder(s).reverse().toString();
return s.equals(reversed);
}
public static void main(String[] args) {
String code = "ABCBA";
System.out.println("Two-pointer: " + twoPointer(code));
System.out.println("Reverse: " + reverseCompare(code));
}
}
Two-pointer: true
Reverse: true
How do you handle case-insensitive palindrome checks?
Real-world palindrome checks often need to ignore case and non-alphanumeric characters. For example, "A man, a plan, a canal: Panama" is a palindrome when you ignore case, spaces, and punctuation. You normalise the input first, then apply the two-pointer scan.
package com.bank.core;
public class NormalisedPalindrome {
public static boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
System.out.println(isPalindrome("A man, a plan, a canal: Panama")); // true
System.out.println(isPalindrome("Rajesh")); // false
}
}
true
false
What are the edge cases?
Edge cases in palindrome checking include empty strings, single characters, strings with all identical characters, and strings with special characters.
package com.bank.core;
public class PalindromeEdgeCases {
public static boolean isPalindrome(String s) {
if (s == null) return false;
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
public static void main(String[] args) {
System.out.println("Empty: " + isPalindrome("")); // true
System.out.println("Single: " + isPalindrome("A")); // true
System.out.println("All same: " + isPalindrome("aaaa")); // true
System.out.println("Two diff: " + isPalindrome("ab")); // false
System.out.println("Null: " + isPalindrome(null)); // false
}
}
Empty: true
Single: true
All same: true
Two diff: false
Null: false
What is the time and space complexity?
The two-pointer palindrome check runs in O(n) time, where n is the length of the string, because each character is visited at most once. The space complexity is O(1) because only two integer index variables are used.
If normalisation is done by creating a cleaned string, the space becomes O(n) for the cleaned copy. The in-place normalisation approach shown above with the skip-non-alphanumeric inner loops avoids this extra allocation and stays at O(1) space.
What are common mistakes?
The most common mistake is using == to compare characters from a String obtained via charAt(). For primitive char values, == works correctly. The real bug is forgetting to handle case sensitivity or forgetting the null check.
package com.bank.core;
public class PalindromeMistakes {
// WRONG: does not handle case
public static boolean wrongPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
public static void main(String[] args) {
// "Madam" should be a palindrome ignoring case, but this returns false
System.out.println("Wrong: " + wrongPalindrome("Madam"));
// Fix by lowercasing
System.out.println("Correct: " + wrongPalindrome("Madam".toLowerCase()));
}
}
Wrong: false
Correct: true
What are common interview follow-up questions?
Interviewers often extend the basic palindrome check with harder variants:
- Valid Palindrome II: can you make the string a palindrome by removing at most one character?
- Longest Palindromic Substring: find the longest contiguous palindrome within a string.
- Palindrome Partitioning: split the string into parts where every part is a palindrome.
- Number Palindrome: check if a number is a palindrome without converting it to a string.
Each of these builds on the two-pointer foundation. Understanding the basic technique thoroughly is the key to solving the variants.
package com.bank.core;
public class PalindromeFollowUp {
// Valid Palindrome II: can remove at most one character
public static boolean validPalindromeII(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return isSubPalindrome(s, left + 1, right)
|| isSubPalindrome(s, left, right - 1);
}
left++;
right--;
}
return true;
}
private static boolean isSubPalindrome(String s, int lo, int hi) {
while (lo < hi) {
if (s.charAt(lo) != s.charAt(hi)) return false;
lo++;
hi--;
}
return true;
}
public static void main(String[] args) {
System.out.println(validPalindromeII("abca")); // true, remove 'c' or 'b'
System.out.println(validPalindromeII("abc")); // false
}
}
true
false
Visual Overview
Two-Pointer Palindrome Check ════════════════════════════ Input: "ABCBA" Index: 0 1 2 3 4 Step 1: left=0 right=4 A == A ✓ move inward Step 2: left=1 right=3 B == B ✓ move inward Step 3: left=2 right=2 pointers meet → palindrome! Input: "ABCDA" Step 1: left=0 right=4 A == A ✓ move inward Step 2: left=1 right=3 B != D ✗ return false
Normalised Palindrome Check ═══════════════════════════ Input: "A man, a plan, a canal: Panama" Step 1: Skip non-alphanumeric from both ends Step 2: Compare lowercased characters left → A right → a (lowercase both → a == a) ✓ left → m right → m ✓ ...continues until pointers meet... Result: palindrome!
Key Takeaway
A palindrome is a string that reads the same forwards and backwards, and the efficient way to check one is the two-pointer technique. Place one pointer at the start and one at the end, compare the two characters, and if they differ return false immediately. If they match, move both pointers inward and repeat until they meet in the middle. If you never find a mismatch, the string is a palindrome. This runs in linear time with constant extra space.
In the banking project at National Bank of India, Rajesh used this in a feature where the system shows a symmetric-code badge when a customer picks a reference code that reads the same both ways. Before running the two-pointer scan, the input is normalised by lowercasing and stripping anything that is not a letter or digit, so a code typed with mixed case or containing spaces is still recognised correctly.
The two-pointer method is preferred over the simpler reverse-and-compare approach because it exits on the very first mismatched pair, which is much faster when the string fails the test early, and it uses only constant extra space, whereas reversing allocates an entire new string. That early-exit plus constant-space combination is the reason interviewers prefer the two-pointer solution.
The technique is also the foundation for harder variants like Valid Palindrome II (remove at most one character), Longest Palindromic Substring, and Palindrome Partitioning. Understanding the basic two-pointer check thoroughly is the key to solving all of them.
Remember one sentence: place two pointers at opposite ends, compare inward, and exit on the first mismatch for an O(n) time, O(1) space palindrome check.
---