Valid Palindrome
EasyUpdated: Aug 2, 2025
Practice on:
Problem
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
[Palindrome Definition](/gk/algorithms/palindrome-definition)
Examples
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
Note
Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.
Similar Problem
[Check if given string is palindrome or not](check-if-given-string-is-palindrome-or-not)
Solution
From start and end loop though the string, i.e., char array. If it is not alpha or number, increase or decrease pointers. Compare the alpha and numeric characters. The solution below is pretty straightforward.
We have seen similar problem - [Check if given string is palindrome or not](check-if-given-string-is-palindrome-or-not).
Video explanation
Here is the video explaining below methods in detail. Please check it out:
<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/plbfvgiCwpQ" frameborder="0" allowfullscreen></iframe></div>
Method 1 - Removing non-alphanumeric chars using regex and check the reversed
Code
Java
class Solution {
public boolean isPalindrome(String s) {
// Preprocess the string using regex: remove non-alphanumeric characters and convert to lowercase
String cleaned = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
// Compare the cleaned string with its reverse
return cleaned.equals(new StringBuilder(cleaned).reverse().toString());
}
}
Python
class Solution:
def isPalindrome(self, s: str) -> bool:
# Preprocess the string using regex
cleaned = re.sub(r"[^a-zA-Z0-9]", "", s).lower() # Remove non-alphanumeric characters and convert to lowercase
# Compare the cleaned string with its reverse
return cleaned == cleaned[::-1]
Method 2 - Removing non-alphanumeric chars manually and loop till middle
Code
Python
class Solution {
public boolean isPalindrome(String s) {
// Preprocess the string: create a clean string manually
StringBuilder cleaned = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) { // Check if the character is alphanumeric
cleaned.append(Character.toLowerCase(c)); // Add lowercase version to the cleaned string
}
}
// Iterate to the middle
int n = cleaned.length();
for (int i = 0; i < n / 2; i++) {
if (cleaned.charAt(i) != cleaned.charAt(n - 1 - i)) { // Compare characters at start and end
return false; // If mismatch occurs, return False
}
}
return true; // If loop completes, return True
}
}
Python
class Solution:
def isPalindrome(self, s: str) -> bool:
# Preprocess the string: create a clean string manually
cleaned = ""
for char in s:
if char.isalnum(): # Check if the character is alphanumeric
cleaned += char.lower() # Add lowercase version to the new string
# Iterate to the middle
n = len(cleaned)
for i in range(n // 2): # Compare up to the middle of the string
if cleaned[i] != cleaned[n - 1 - i]: # Compare characters at start and end
return False # If mismatch occurs, return False
return True # If loop completes, return True
Method 3 - Removing non-alphanumeric chars and using 2 Pointers
Code
Java
class Solution {
public boolean isPalindrome(String s) {
// Step 1: Build the cleaned string manually
StringBuilder cleaned = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) { // Use a custom method to check if it's alphanumeric
cleaned.append(Character.toLowerCase(c)); // Use a custom method to convert to lowercase
}
}
// Step 2: Use two pointers to check for palindrome
int left = 0, right = cleaned.length() - 1;
while (left < right) {
if (cleaned.charAt(left) != cleaned.charAt(right)) { // Compare characters at both pointers
return false; // If mismatch, return false
}
left++; // Move left pointer inward
right--; // Move right pointer inward
}
return true; // If no mismatches, string is a palindrome
}
}
Python
class Solution:
def isPalindrome(self, s: str) -> bool:
# Preprocess the string: create a clean string manually
cleaned = ""
for char in s:
if char.isalnum(): # Check if the character is alphanumeric
cleaned += char.lower() # Add its lowercase version to the new string
# Initialise two pointers
left, right = 0, len(cleaned) - 1
# Compare characters at each pointer
while left < right:
if cleaned[left] != cleaned[right]: # If mismatch, return False
return False
left += 1
right -= 1
return True # If the loop completes, return True
Complexity
- ⏰ Time complexity:
O(n) - 🧺 Space complexity:
O(1)
Method 4 - Using 2 pointers - No preprocessing
Code
Java
class Solution {
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !Character.isLetterOrDigit(s.charAt(l))) {
l++;
}
while (l < r && !Character.isLetterOrDigit(s.charAt(r))) {
r--;
}
if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
return false;
}
l++;
r--;
}
return true;
}
}
Python
class Solution:
def is_palindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return True
Complexity
- ⏰ Time complexity:
O(n) - 🧺 Space complexity:
O(1)
Method 5 - Using 2 pointers - No shortcuts with built-ins
Code
Java
class Solution {
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !myIsLetterOrDigit(s.charAt(l))) {
l++;
}
while (l < r && !myIsLetterOrDigit(s.charAt(r))) {
r--;
}
if (myToLowerCase(s.charAt(l)) !=
myToLowerCase(s.charAt(r))) {
return false;
}
l++;
r--;
}
return true;
}
// UDF to check if a character is alphanumeric
private boolean isLetterOrDigit(char c) {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
}
// UDF to convert uppercase to lowercase
private char toLowerCase(char c) {
if (c >= 'A' && c <= 'Z') {
return (char) (c + 32); // Add 32 to ASCII value for conversion
}
return c; // Return as-is for lowercase letters or non-letters
}
}
Python
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not self.isalnum(s[l]):
l += 1
while l < r and not self.isalnum(s[r]):
r -= 1
if self.lower(s[l]) != self.lower(s[r]):
return False
l += 1
r -= 1
return True
# UDF to check if a character is alphanumeric
def isalnum(self, char: str) -> bool:
return ('a' <= char <= 'z') or \
('A' <= char <= 'Z') or \
('0' <= char <= '9')
# UDF to convert uppercase to lowercase
def lower(self, char: str) -> str:
if 'A' <= char <= 'Z':
return chr(ord(char) + 32) # Add 32 to ASCII value for conversion
return char # Return as-is for lowercase letters or non-letters
Complexity
- ⏰ Time complexity:
O(n) - 🧺 Space complexity:
O(1)
Method 6 - Using Stack
This solution removes the special characters first.
Code
Java
public boolean isPalindrome(String s) {
// a shortcut
s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
int len = s.length();
if (len < 2) {
return true;
}
Stack<Character> stack = new Stack<Character>();
int index = 0;
while (index < len / 2) {
stack.push(s.charAt(index));
index++;
}
if (len % 2 == 1) {
index++;
}
while (index < len) {
if (stack.empty()) {
return false;
}
char temp = stack.pop();
if (s.charAt(index) != temp) {
return false;
} else {
index++;
}
}
return true;
}
Complexity
- ⏰ Time complexity:
O(n) - 🧺 Space complexity:
O(n)