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 * 105s consists only of printable ASCII characters.The Valid Palindrome problem asks you to determine whether a string reads the same forward and backward after ignoring non-alphanumeric characters and letter case. The most efficient strategy uses the two pointers technique.
Start with one pointer at the beginning of the string and another at the end. Move each pointer inward while skipping characters that are not letters or digits using checks like isalnum(). Before comparing characters, normalize them to the same case using tolower() or an equivalent method. If the characters at both pointers ever differ, the string is not a palindrome.
This method avoids creating additional filtered strings and instead validates the palindrome directly in a single pass. Because each character is processed at most once, the approach runs efficiently in linear time. The algorithm also maintains constant extra space since it only uses a few pointer variables.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers with character skipping | O(n) | O(1) |
| Build filtered string then check palindrome | O(n) | O(n) |
NeetCode
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.
Time Complexity: O(n), where n is the length of the string, because we go through the string at most once.
Space Complexity: O(1), as we use a constant amount of space.
1#include <stdio.h>
2#include <ctype.h>
3#include <stdbool.h>
4
5bool isPalindrome(char *s) {
6
This C program reads characters from both ends of the string, moving pointers inward while ignoring non-alphanumeric characters. It checks for equality and converts characters to lowercase for case insensitivity. It returns false if a mismatch is found; otherwise, true.
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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), because the cleaned string and its reverse require extra space proportional to n.
1class Solution:
2 def isPalindrome
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Valid Palindrome is a common entry-level interview question in companies like Google, Amazon, and Meta. It tests understanding of string manipulation, edge case handling, and the two-pointer technique.
The optimal approach uses the two-pointer technique. One pointer starts from the left and another from the right, skipping non-alphanumeric characters and comparing normalized characters. This allows the check to be completed in one pass with constant extra space.
No special data structure is required for the optimal solution. Simple string traversal with two indices is sufficient. This keeps the space complexity minimal while maintaining linear runtime.
The problem statement specifies that only letters and digits should be considered when checking for a palindrome. Ignoring punctuation and spaces ensures that phrases like 'A man, a plan, a canal: Panama' are correctly identified as palindromes.
This Python solution filters the input to ignore non-alphanumeric characters and reverses the filtered string for comparison, aggressive and straightforward for detecting palindromes.