Definition
- Valid palindrome check – determines whether a string reads the same forward and backward after ignoring non-alphanumeric characters and treating letters case-insensitively.
- Opposite-end two pointers – a
leftpointer starts at position 0 and arightpointer starts at the last position, moving toward each other. - Skip non-alphanumeric – each pointer advances past characters where
Character.isLetterOrDigitreturns false before comparing. - Case-insensitive comparison –
Character.toLowerCaseis applied to both characters before checking equality. - O(n) time, O(1) space – each character is examined at most once, and no extra string is allocated.
At the National Bank of India, printed reference codes contain dashes and spaces for readability, but an internal checksum rule requires the alphanumeric core to be symmetric. Rajesh reads from both ends toward the middle, skipping any dash or space, and checks that each matching pair of real characters is the same letter or digit regardless of case.
Understanding the Concepts
What is the Valid Palindrome problem?
The problem asks whether a given string is a palindrome after ignoring all non-alphanumeric characters and treating uppercase and lowercase letters as equal. For example, the string "A man, a plan, a canal: Panama" is a valid palindrome because after removing punctuation and spaces and lowercasing, it reads amanaplanacanalpanama, which is the same forwards and backwards.
package com.bank.core;
// Input: "A man, a plan, a canal: Panama"
// Cleaned: "amanaplanacanalpanama"
// This reads the same forwards and backwards -> valid palindrome
Why use two pointers instead of cleaning and reversing?
The naive approach strips all non-alphanumeric characters into a new string, reverses it, and compares. This works but allocates O(n) extra space for the cleaned string and O(n) for the reversed copy. The two-pointer approach achieves the same result in O(1) extra space by working directly on the original string.
package com.bank.core;
// NAIVE: O(n) extra space
String cleaned = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
String reversed = new StringBuilder(cleaned).reverse().toString();
return cleaned.equals(reversed);
// TWO POINTERS: O(1) extra space
// Work directly on original string, skip non-alphanumeric in place
How do the two pointers work?
You set left = 0 and right = s.length() - 1. The outer loop runs while left < right. Inside, you first advance left past any character where Character.isLetterOrDigit is false, and similarly retreat right past non-alphanumeric characters. Once both pointers rest on alphanumeric characters, you compare them after lowercasing. If they differ, it is not a palindrome and you return false. If they match, you move both inward and continue.
package com.bank.service;
public class PalindromeValidator {
public 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) {
PalindromeValidator validator = new PalindromeValidator();
System.out.println(validator.isPalindrome("A man, a plan, a canal: Panama"));
System.out.println(validator.isPalindrome("race a car"));
System.out.println(validator.isPalindrome(" "));
}
}
true
false
true
Why must the inner skip loops check left < right?
The inner loops that skip non-alphanumeric characters must include the guard left < right. Without this guard, on a string that is entirely punctuation or has a long tail of punctuation, the left pointer could advance past the right pointer, causing an out-of-bounds comparison or comparing characters that have already been passed.
package com.bank.core;
// WRONG: inner loop without guard
while (!Character.isLetterOrDigit(s.charAt(left))) left++;
// On input "!!!" this runs off the end of the string
// CORRECT: inner loop with guard
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
// On input "!!!" the pointers meet and the outer loop exits cleanly
What are the edge cases?
Several edge cases are important: an empty string is a valid palindrome because the pointers meet immediately, a string of only punctuation is valid for the same reason, a single character is always a palindrome, and strings with mixed digits and letters must compare digits against digits and letters against letters.
package com.bank.core;
// Edge case 1: empty string "" -> true (pointers meet immediately)
// Edge case 2: all punctuation ".,!" -> true (pointers skip everything)
// Edge case 3: single char "a" -> true (left == right, loop does not run)
// Edge case 4: "0P" -> false ('0' != 'p', digit vs letter)
// Edge case 5: "Aa" -> true ('a' == 'a' after lowercasing)
How does this compare to using a cleaned StringBuilder?
Both approaches produce the correct answer, but they differ in space usage and allocation cost. The two-pointer approach is preferred in interviews because it demonstrates in-place thinking.
| Approach | Time | Space | Allocations |
|---|---|---|---|
| Two pointers on original | O(n) | O(1) | None |
| Clean + reverse | O(n) | O(n) | New string + reversed copy |
| Clean + two pointers | O(n) | O(n) | New cleaned string |
package com.bank.service;
// Clean + reverse approach (works but wastes space)
public class CleanReverseValidator {
public boolean isPalindrome(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
sb.append(Character.toLowerCase(c));
}
}
String cleaned = sb.toString();
return cleaned.equals(sb.reverse().toString());
}
}
What about a banking use case?
At the National Bank of India, printed reference codes contain dashes and spaces for human readability, but a legacy checksum rule requires the alphanumeric core to be a palindrome. Rajesh validates each code during batch processing without allocating extra strings.
package com.bank.service;
public class ReferenceCodeValidator {
private final PalindromeValidator palindromeValidator = new PalindromeValidator();
public boolean isValidChecksum(String referenceCode) {
if (referenceCode == null || referenceCode.isEmpty()) {
return true; // empty code is trivially valid
}
return palindromeValidator.isPalindrome(referenceCode);
}
public static void main(String[] args) {
ReferenceCodeValidator validator = new ReferenceCodeValidator();
String code1 = "NBI-121-IBN";
String code2 = "HDFC-9009-CFHD";
String code3 = "ICICI-2024";
System.out.println(code1 + " valid: " + validator.isValidChecksum(code1));
System.out.println(code2 + " valid: " + validator.isValidChecksum(code2));
System.out.println(code3 + " valid: " + validator.isValidChecksum(code3));
}
}
NBI-121-IBN valid: true
HDFC-9009-CFHD valid: true
ICICI-2024 valid: false
What are common mistakes?
The most common mistake is forgetting the guard on the inner skip loops, which causes index-out-of-bounds on strings that are entirely punctuation. Another mistake is comparing characters without lowercasing, which fails on mixed-case palindromes. A third mistake is using Character.isAlphabetic instead of Character.isLetterOrDigit, which excludes digits from the comparison.
package com.bank.core;
// WRONG: using isAlphabetic (excludes digits)
while (left < right && !Character.isAlphabetic(s.charAt(left))) left++;
// Input "121" would skip all digits, treating it as empty
// CORRECT: using isLetterOrDigit (includes digits)
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
// Input "121" correctly checks 1-2-1 as a palindrome
What should a senior engineer know?
A senior engineer should note that Character.toLowerCase handles Unicode correctly, unlike a manual c - 'A' + 'a' cast that only works for ASCII. For production code processing international account names, the Unicode-aware methods are essential. The two-pointer palindrome check is also the building block for more advanced problems like longest palindromic substring (expand-around-center) and palindrome partitioning.
package com.bank.core;
// Unicode-safe: Character.toLowerCase handles all scripts
// ASCII-only shortcut: (char)(c - 'A' + 'a') fails on non-ASCII
// Time: O(n) single pass, each character visited at most once
// Space: O(1) no extra allocation
// This is the foundation for expand-around-center palindrome problems
Visual Overview
Two-pointer palindrome check:
Input: "N B I - 1 2 1 - I B N"
^ ^
left right
Step 1: Both on alphanumeric
┌─────────────────────────────────────┐
│ left='N', right='N' │
│ toLowerCase: 'n' == 'n' -> match │
│ Move both inward │
└─────────────────────────────────────┘
Step 2: Skip spaces, land on next
┌─────────────────────────────────────┐
│ left='B', right='B' │
│ toLowerCase: 'b' == 'b' -> match │
│ Move both inward │
└─────────────────────────────────────┘
Step 3: Skip spaces
┌─────────────────────────────────────┐
│ left='I', right='I' │
│ toLowerCase: 'i' == 'i' -> match │
│ Move both inward │
└─────────────────────────────────────┘
Step 4: Skip dashes
┌─────────────────────────────────────┐
│ left='1', right='1' │
│ '1' == '1' -> match │
│ Move both inward │
└─────────────────────────────────────┘
Step 5: Pointers meet at center
┌─────────────────────────────────────┐
│ left='2', right='2' (same index) │
│ left < right is false -> exit loop │
│ Return TRUE: valid palindrome │
└─────────────────────────────────────┘
Pointer movement:
N B I - 1 2 1 - I B N
^ ^
L→ → → skip → ← skip ← ← ←R
───▶ ◀───
pointers meet in center
Key Takeaway
Valid Palindrome checks whether a string reads the same forward and backward once you ignore everything that is not a letter or digit and treat letters case-insensitively. The two-pointer approach solves this in O(n) time and O(1) space by working directly on the original string. A left pointer starts at the front and a right pointer starts at the back, each skipping non-alphanumeric characters before comparing the lowercased values.
The critical correctness detail is guarding the inner skip loops with the same left < right condition as the outer loop. Without that guard, the pointers can cross each other while skipping punctuation, causing out-of-bounds reads. This guard also makes strings that are entirely punctuation or empty come out as valid palindromes, because the pointers simply meet immediately.
The naive approach of stripping non-alphanumeric characters into a new string, reversing it, and comparing works but wastes O(n) space on allocations that the two-pointer method avoids entirely. In an interview, demonstrating the in-place approach shows you understand both the algorithmic pattern and the practical concern of avoiding unnecessary allocations.
At the National Bank of India, Rajesh used this to validate printed reference codes that contained dashes and spaces for readability but required the alphanumeric core to be a palindrome under a legacy checksum rule. The two-pointer validator handled edge cases like all-separator codes and mixed-case inputs without any extra allocation, processing millions of codes in the nightly batch.
Remember one sentence: use two pointers from both ends, skip non-alphanumeric characters with a guarded inner loop, compare lowercased values, and return true if the pointers meet without a mismatch.
---