Valid Palindrome solution and explanation
Deloitte
Infosys
9 more videos on this problem
Valid Palindrome - Leetcode 125 - PythonNeetCode · 14:58 · 419K views
LeetCode Valid Palindrome Solution Explained - JavaNick White · 5:27 · 46K views
Valid Palindrome | LeetCode problem 125 | Top 150 interview question seriesTechnosage · 5:43 · 46K views
Valid Palindrome - Leetcode 125 - 2 Pointers (Python)Greg Hogg · 5:43 · 22K views
Valid Palindrome | LeetCode 125 | C++, Java, PythonKnowledge Center · 10:38 · 19K views
Palindromes | Valid Palindrome (LeetCode 125, 9) | Simplified visuals and animationsNikhil Lohia · 13:52 · 16K views
Leetcode | 125. Valid Palindrome | Easy | Java SolutionDeveloper Docs · 6:46 · 7K views
Valid Palindrome - LeetCode 125 - JavaScriptAlgoJS · 5:39 · 4K views
Valid Palindrome - LeetCode 125 - PythonDeepti Talesra · 12:10 · 3K views
Valid Palindrome | LeetCode 125 | Programming TutorialsProgramming Tutorials · 10:57 · 2K views
The problem
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
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.
Constraints:
1 <= s.length <= 2 * 105sconsists only of printable ASCII characters.
Approach overview
Problem Overview: You receive a string that may contain letters, digits, spaces, and punctuation. Determine whether it reads the same forward and backward after ignoring non‑alphanumeric characters and treating uppercase and lowercase letters as equal.
Approach 1: String Normalization and Reverse Comparison (O(n) time, O(n) space)
The straightforward solution is to first normalize the string. Iterate through each character, keep only alphanumeric characters, and convert them to lowercase. Store the cleaned characters in a new string or array. Once normalized, check whether this string equals its reverse using reverse() or slicing like s[::-1] in Python. This works because the preprocessing step removes everything that should be ignored by the palindrome check. The tradeoff is extra memory since you build a new string of size up to n, giving O(n) space complexity.
This method is easy to implement and highly readable. If clarity matters more than memory usage, or if you're quickly validating input before other processing, normalization followed by reverse comparison is perfectly acceptable. The approach mainly relies on basic string manipulation operations.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The optimal solution avoids building a new string. Instead, use two indices: one starting at the beginning of the string and one at the end. Move both pointers toward the center while skipping characters that are not alphanumeric. When both pointers land on valid characters, compare them after converting to lowercase. If they differ, the string cannot be a palindrome. If they match, continue moving inward until the pointers cross.
This method performs a single pass through the string, so the time complexity remains O(n). However, it uses constant extra memory because it compares characters directly in the original string. The logic is a classic application of two pointers, where symmetric positions are validated without allocating additional structures.
The key insight is that characters that don't affect the palindrome condition can simply be skipped during traversal. Instead of preprocessing the entire string, filtering happens on the fly. This reduces memory usage and keeps the algorithm efficient even for large inputs.
Recommended for interviews: Interviewers expect the Two-Pointer Technique. The normalization approach shows that you understand the problem constraints, but the two-pointer version demonstrates stronger algorithmic thinking and space optimization. It also appears frequently in other string and two‑pointer interview problems where symmetric comparisons are required.
Approach 1: Two-Pointer Technique
This approach employs two pointers: one starting at the beginning of the string and the other at the end. The algorithm checks if the characters at these pointers are the same, ignoring case and non-alphanumeric characters. If they match, both pointers move inward. If they don't or if any pointer surpasses the other, the string is not a palindrome.
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
# Usage
solution = Solution()
print(solution.isPalindrome("A man, a plan, a canal: Panama"))public class Solution {
public boolean isPalindrome(String s) {
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--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "A man, a plan, a canal: Panama";
System.out.println(solution.isPalindrome(s));
}
}#include <iostream>
#include <cctype>
bool isPalindrome(std::string s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !std::isalnum(s[left])) left++;
while (left < right && !std::isalnum(s[right])) right--;
if (std::tolower(s[left]) != std::tolower(s[right])) return false;
left++;
right--;
}
return true;
}
int main() {
std::string s = "A man, a plan, a canal: Panama";
if (isPalindrome(s)) {
std::cout << "true" << std::endl;
} else {
std::cout << "false" << std::endl;
}
return 0;
}const isPalindrome = function(s) {
let left = 0, right = s.length - 1;
while (left < right) {
while (left < right && !(/[a-zA-Z0-9]/).test(s[left])) left++;
while (left < right && !(/[a-zA-Z0-9]/).test(s[right])) right--;
if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
left++;
right--;
}
return true;
};
// Test
console.log(isPalindrome("A man, a plan, a canal: Panama"));#include <stdio.h>
#include <ctype.h>
#include <stdbool.h>
bool isPalindrome(char *s) {
int left = 0, right = strlen(s) - 1;
while (left < right) {
while (left < right && !isalnum(s[left])) left++;
while (left < right && !isalnum(s[right])) right--;
if (tolower(s[left]) != tolower(s[right])) return false;
left++;
right--;
}
return true;
}
int main() {
char s[] = "A man, a plan, a canal: Panama";
if (isPalindrome(s)) {
printf("true\n");
} else {
printf("false\n");
}
return 0;
}using System;
public class Solution {
public bool IsPalindrome(string s) {
int left = 0, right = s.Length - 1;
while (left < right) {
while (left < right && !Char.IsLetterOrDigit(s[left])) left++;
while (left < right && !Char.IsLetterOrDigit(s[right])) right--;
if (Char.ToLower(s[left]) != Char.ToLower(s[right])) return false;
left++;
right--;
}
return true;
}
public static void Main() {
Solution solution = new Solution();
string s = "A man, a plan, a canal: Panama";
Console.WriteLine(solution.IsPalindrome(s));
}
}This Python function checks if a given string is a palindrome by comparing characters from both directions. It skips non-alphanumeric characters and compares the rest while ignoring case, returning the correct result accordingly.
Time Complexity: O(n), where n is the length of the input.
Space Complexity: O(1), due to in-place operations.
Approach 2: String Normalization and Reverse Comparison
This approach first cleans the input string by removing non-alphanumeric characters and converting all letters to lowercase. It then compares the normalized string to its reverse to determine if it is a palindrome.
class Solution:
def isPalindrome(self, s: str) -> bool:
filtered = ''.join(ch.lower() for ch in s if ch.isalnum())
return filtered == filtered[::-1]
# Usage
solution = Solution()
print(solution.isPalindrome("A man, a plan, a canal: Panama"))#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
bool isPalindrome(std::string s) {
std::string filtered = "";
for (char c : s) {
if (std::isalnum(c)) {
filtered += std::tolower(c);
}
}
std::string reversed = filtered;
std::reverse(reversed.begin(), reversed.end());
return filtered == reversed;
}
int main() {
std::string s = "A man, a plan, a canal: Panama";
if (isPalindrome(s)) {
std::cout << "true" << std::endl;
} else {
std::cout << "false" << std::endl;
}
return 0;
}const isPalindrome = function(s) {
const filtered = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
return filtered === filtered.split('').reverse().join('');
};
// Test
console.log(isPalindrome("A man, a plan, a canal: Panama"));This Python solution filters the input to ignore non-alphanumeric characters and reverses the filtered string for comparison, aggressive and straightforward for detecting palindromes.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to the additional normalized string storage.
Approach 3: Two Pointers
We use two pointers i and j to point to the two ends of the string s, and then loop through the following process until i geq j:
- If
s[i]is not a letter or a number, move the pointerione step to the right and continue to the next loop. - If
s[j]is not a letter or a number, move the pointerjone step to the left and continue to the next loop. - If the lowercase form of
s[i]ands[j]are not equal, returnfalse. - Otherwise, move the pointer
ione step to the right and the pointerjone step to the left, and continue to the next loop.
At the end of the loop, return true.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
function isPalindrome(s: string): boolean {
let i = 0;
let j = s.length - 1;
while (i < j) {
if (!/[a-zA-Z0-9]/.test(s[i])) {
++i;
} else if (!/[a-zA-Z0-9]/.test(s[j])) {
--j;
} else if (s[i].toLowerCase() !== s[j].toLowerCase()) {
return false;
} else {
++i;
--j;
}
}
return true;
}func isPalindrome(s string) bool {
i, j := 0, len(s)-1
for i < j {
if !isalnum(s[i]) {
i++
} else if !isalnum(s[j]) {
j--
} else if tolower(s[i]) != tolower(s[j]) {
return false
} else {
i, j = i+1, j-1
}
}
return true
}
func isalnum(ch byte) bool {
return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')
}
func tolower(ch byte) byte {
if ch >= 'A' && ch <= 'Z' {
return ch + 32
}
return ch
}impl Solution {
pub fn is_palindrome(s: String) -> bool {
let s = s.to_lowercase();
let s = s.as_bytes();
let n = s.len();
let (mut l, mut r) = (0, n - 1);
while l < r {
while l < r && !s[l].is_ascii_alphanumeric() {
l += 1;
}
while l < r && !s[r].is_ascii_alphanumeric() {
r -= 1;
}
if s[l] != s[r] {
return false;
}
l += 1;
if r != 0 {
r -= 1;
}
}
true
}
}class Solution {
/**
* @param String $s
* @return Boolean
*/
function isPalindrome($s) {
$regex = '/[a-z0-9]/';
$s = strtolower($s);
preg_match_all($regex, $s, $matches);
if ($matches[0] == null) {
return true;
}
$len = floor(count($matches[0]) / 2);
for ($i = 0; $i < $len; $i++) {
if ($matches[0][$i] != $matches[0][count($matches[0]) - 1 - $i]) {
return false;
}
}
return true;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n), where n is the length of the input. |
| String Normalization and Reverse Comparison | Time Complexity: O(n), where n is the length of the string. |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| String Normalization + Reverse Comparison | O(n) | O(n) | When readability matters and extra memory is acceptable |
| Two-Pointer Technique | O(n) | O(1) | Best for interviews and large inputs where constant space is preferred |
Frequently asked questions
Is Valid Palindrome easy or hard?
Valid Palindrome is classified as an Easy problem on LeetCode with an acceptance rate around 50%. The logic is simple once you recognize the two-pointer pattern, but it still checks whether you handle character filtering and case normalization correctly.
How to solve Valid Palindrome in O(n)?
Use two pointers that start at the left and right ends of the string. Move each pointer inward while skipping characters that are not letters or digits. Compare the lowercase versions of the characters at both pointers; if all pairs match, the string is a valid palindrome. This requires a single pass through the string.
What is the best approach for Valid Palindrome?
The two-pointer technique is the best approach. Start one pointer at the beginning and another at the end of the string, skip non-alphanumeric characters, and compare characters after converting them to lowercase. This method runs in O(n) time and uses O(1) extra space, which is optimal for this problem.
What data structure is used in Valid Palindrome?
The optimal solution does not require additional data structures and works directly on the string using two pointers. Some simpler implementations create a filtered string or character array before comparing it with its reverse.
What is the time complexity of Valid Palindrome?
The optimal solution runs in O(n) time where n is the length of the string. Each character is visited at most once while moving two pointers from both ends toward the center. Space complexity can be O(1) with the two-pointer method or O(n) if you create a normalized copy of the string.
Valid Palindrome Python or Java solution approach?
In both Python and Java, the typical solution uses two pointers and built-in character checks such as isalnum() in Python or Character.isLetterOrDigit() in Java. Convert characters to lowercase and compare them while moving the pointers inward. The algorithm runs in O(n) time with constant extra space.
Is Valid Palindrome asked at Google, Amazon, or Meta?
Valid Palindrome is a common easy-level interview question asked by companies such as Amazon, Meta, Google, and Microsoft. It tests understanding of string traversal, character filtering, and the two-pointer pattern frequently used in interview problems.