Definition
- Two-pointer technique places one pointer at the front and one at the back, moving them toward the center.
- Skip non-alphanumeric uses
Character.isLetterOrDigit()to advance each pointer past spaces, punctuation, and symbols. - Case-insensitive comparison uses
Character.toLowerCase()on both characters so uppercase and lowercase letters match. - Fail-fast exit returns false immediately on the first mismatch without scanning the rest of the string.
- Constant space is achieved by comparing in place on the original string rather than building a cleaned copy.
The National Bank of India validates vanity account nicknames that are supposed to be symmetric, like a mirror, ignoring spaces, punctuation, and capitalization. Two fingers start at the first and last meaningful characters. If either finger lands on a space or a symbol, that finger steps past it. Then the two meaningful characters are compared ignoring case. If they ever differ, it is not symmetric. If the fingers meet in the middle without a mismatch, it is a valid palindrome.
Understanding the Concepts
What is a palindrome check?
A palindrome check determines whether a string reads the same forward and backward. For practical purposes, the check ignores case and non-alphanumeric characters. The string "A man, a plan, a canal: Panama" is a palindrome because after removing spaces, commas, and the colon, and ignoring case, it reads "amanaplanacanalpanama" which is symmetric.
package com.bank.validation;
public class PalindromeChecker {
public static boolean isPalindrome(String s) {
if (s == null) return false;
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;
}
}
Why does this matter in banking?
The National Bank of India runs a rewards promotion where customers can pick vanity account nicknames. Palindromic nicknames get bonus points. Rajesh validates each submission by checking whether the nickname reads the same both ways, ignoring spaces and case, running on every submission with no extra allocation.
package com.bank.service;
import com.bank.validation.PalindromeChecker;
public class NicknameService {
public boolean isEligibleForBonus(String nickname) {
boolean palindrome = PalindromeChecker.isPalindrome(nickname);
System.out.println("Nickname '" + nickname + "' is palindrome: " + palindrome);
return palindrome;
}
public static void main(String[] args) {
NicknameService service = new NicknameService();
service.isEligibleForBonus("Racecar");
service.isEligibleForBonus("Savings");
service.isEligibleForBonus("A Santa at NASA");
}
}
Nickname 'Racecar' is palindrome: true
Nickname 'Savings' is palindrome: false
Nickname 'A Santa at NASA' is palindrome: true
How does the two-pointer technique work step by step?
Start with left at index 0 and right at the last index. In each iteration, advance left forward past any non-alphanumeric characters, and advance right backward past any non-alphanumeric characters. Now both pointers sit on meaningful characters. Compare them case-insensitively. If they differ, return false. If they match, move both pointers inward by one and repeat until they meet.
package com.bank.validation;
public class StepByStepDemo {
public static void main(String[] args) {
String s = "A,b,B,a";
int left = 0, 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--;
char lc = Character.toLowerCase(s.charAt(left));
char rc = Character.toLowerCase(s.charAt(right));
System.out.println("Compare s[" + left + "]='" + lc + "' with s[" + right + "]='" + rc + "'");
if (lc != rc) { System.out.println("Mismatch!"); return; }
left++;
right--;
}
System.out.println("Palindrome!");
}
}
Compare s[0]='a' with s[7]='a'
Compare s[2]='b' with s[5]='b'
Palindrome!
How is this different from the naive approach?
The naive approach cleans the string first by removing non-alphanumeric characters and lowercasing, then reverses it and compares. That works but allocates two extra strings. The two-pointer approach avoids all allocation by comparing in place, skipping unwanted characters as it goes.
| Aspect | Naive (clean + reverse) | Two-pointer (in-place) |
|---|---|---|
| Extra space | O(n) for cleaned string | O(1) |
| Time | O(n) | O(n) |
| Allocations | 2 new strings | None |
| Readability | Simpler | Slightly more complex |
package com.bank.validation;
public class NaiveVsTwoPointer {
// Naive approach: allocates extra strings
public static boolean naivePalindrome(String s) {
String cleaned = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
return cleaned.equals(new StringBuilder(cleaned).reverse().toString());
}
public static void main(String[] args) {
String test = "A Santa at NASA";
System.out.println("Naive: " + naivePalindrome(test));
System.out.println("Two-pointer: " + PalindromeChecker.isPalindrome(test));
}
}
Naive: true
Two-pointer: true
What are the edge cases?
An empty string is a palindrome because there are no characters to contradict symmetry. A single character is always a palindrome. A string of only punctuation like ",.!" is a palindrome because after skipping all non-alphanumeric characters, there is nothing left to mismatch. Null input should return false by convention.
package com.bank.validation;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(PalindromeChecker.isPalindrome("")); // true
System.out.println(PalindromeChecker.isPalindrome("a")); // true
System.out.println(PalindromeChecker.isPalindrome(",.!")); // true
System.out.println(PalindromeChecker.isPalindrome(null)); // false
System.out.println(PalindromeChecker.isPalindrome("ab")); // false
}
}
true
true
true
false
false
What are common mistakes?
The most dangerous mistake is forgetting the left < right guard inside the inner skip loops. Without it, a string of only punctuation causes the pointers to run past each other, resulting in an index-out-of-bounds exception. The second mistake is comparing characters without lowercasing, which makes "Racecar" fail despite being a valid palindrome.
package com.bank.validation;
public class CommonMistakesDemo {
// WRONG: no guard in skip loop, no case folding
public static boolean buggyPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (!Character.isLetterOrDigit(s.charAt(l))) l++; // may go out of bounds
while (!Character.isLetterOrDigit(s.charAt(r))) r--; // may go out of bounds
if (s.charAt(l) != s.charAt(r)) return false; // case-sensitive (bug)
l++; r--;
}
return true;
}
// CORRECT: guarded skip loops and case folding
public static void main(String[] args) {
// buggyPalindrome(",.!") would throw StringIndexOutOfBoundsException
System.out.println(PalindromeChecker.isPalindrome(",.!")); // true (safe)
System.out.println(PalindromeChecker.isPalindrome("Racecar")); // true (case-insensitive)
}
}
true
true
What about Unicode and locale issues?
Character.toLowerCase() works for ASCII but full Unicode case folding can be locale-sensitive. For example, the Turkish dotless i has different uppercase behavior. For bank nicknames restricted to ASCII letters and digits, this is not a concern. For internationalized input, a locale-aware normalization would be needed.
package com.bank.validation;
import java.util.Locale;
public class LocaleDemo {
public static void main(String[] args) {
char lower = 'i';
System.out.println("Default upper: " + Character.toUpperCase(lower));
System.out.println("Turkish upper: " + String.valueOf(lower).toUpperCase(new Locale("tr")));
}
}
What is the time and space complexity?
Time is O(n) because each pointer traverses the string at most once. Space is O(1) because no extra data structures or strings are created. The early return on the first mismatch makes typical non-palindromes fast because they often fail near the ends.
What are common interview follow-up questions?
- How would you check if a string can become a palindrome by removing at most one character?
- How would you find the longest palindromic substring?
- How would you count all palindromic substrings in a string?
- What is the difference between a palindrome check and an anagram check?
Visual Overview
Input: "A Santa at NASA"
left=0 right=14
│ │
▼ ▼
[A] , S a n t a a t N A S [A]
Step 1: s[0]='A', s[14]='A' ── match (a == a)
Step 2: skip ',' and ' ' ── s[2]='S', s[13]='S' ── match
Step 3: s[3]='a', s[12]='A' ── match (a == a)
Step 4: s[4]='n', s[11]='N' ── match (n == n)
Step 5: s[5]='t', skip ' ' ── s[9]='t' ── match
Step 6: s[6]='a', s[8]='a' ── match
Step 7: left >= right ── done ── palindrome!
┌──────────────────────────────────┐
│ Two-Pointer Palindrome Check │
│ │
│ left ──→ skip non-alnum ──→ │
│ right ←── skip non-alnum ←── │
│ │
│ Compare toLowerCase(left) │
│ vs toLowerCase(right) │
│ │
│ Match? ── move both inward │
│ Mismatch? ── return false │
│ left >= right? ── return true │
└──────────────────────────────────┘
Key Takeaway
The palindrome check with two pointers is one of the cleanest examples of the two-pointer technique in string problems. Rajesh at the National Bank of India validates vanity account nicknames by placing one pointer at the front and one at the back, advancing each past non-alphanumeric characters, and comparing the meaningful characters case-insensitively. The moment the two characters differ, the check returns false. If the pointers meet in the middle without a mismatch, the string is a palindrome.
The key advantage over the naive approach is constant extra space. Instead of building a cleaned copy of the string and then reversing it, the two-pointer method works directly on the original string by skipping unwanted characters in the loop. Each pointer traverses the string at most once, giving O(n) time with O(1) space.
The detail that separates a correct solution from a buggy one is the guard condition inside the skip loops. Each inner skip must check that left < right before advancing, otherwise a string of only punctuation causes the pointers to run past each other and crash with an index-out-of-bounds exception. With the guard, an all-punctuation string correctly returns true because it has no meaningful characters to contradict symmetry.
For internationalized input beyond ASCII, Character.toLowerCase() may not handle locale-specific case rules correctly. The Turkish dotless i is the classic example. For bank nicknames restricted to ASCII letters and digits, this is not a concern. For full Unicode support, a locale-aware normalization would be needed before comparison.
Remember one sentence: two pointers walk inward, skip non-alphanumeric, compare case-insensitively, and return false on the first mismatch or true when they meet.
---