Valid Palindrome
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves creating a new string by filtering out non-alphanumeric characters and converting all letters to lowercase. Then, this new string is compared with its reversed version to determine if it's a palindrome.
Algorithm
- Initialize an empty
StringBuilder, let's call itfilteredBuilder. - Iterate through each character
cof the input strings. - If
cis an alphanumeric character: a. Convertcto its lowercase equivalent. b. Append the lowercase character tofilteredBuilder. - Convert
filteredBuilderto a string,filteredString. - Create a new string,
reversedString, which is the reverse offilteredString. - Compare
filteredStringandreversedString. If they are equal, returntrue. Otherwise, returnfalse.
Walkthrough
First, we iterate through the input string s. We use a StringBuilder to build a new string. For each character in s, we check if it's a letter or a digit using Character.isLetterOrDigit(). If it is, we convert it to lowercase using Character.toLowerCase() and append it to our StringBuilder. After iterating through the entire input string, we have a "cleaned" version. We then create a reversed version of this cleaned string. Finally, we compare the cleaned string with its reversed counterpart. If they are identical, the original string is a palindrome.
class Solution { public boolean isPalindrome(String s) { StringBuilder filteredString = new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isLetterOrDigit(c)) { filteredString.append(Character.toLowerCase(c)); } } String original = filteredString.toString(); String reversed = filteredString.reverse().toString(); return original.equals(reversed); }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
Simple and easy to understand.
Separates the concerns of filtering and palindrome checking.
Cons
Inefficient in terms of space. It requires creating at least one, and in this specific implementation, two new strings whose size can be up to the original string's length.
This method first filters the string to keep only alphanumeric characters (in lowercase), similar to the first approach. However, instead of creating a reversed copy, it uses a two-pointer technique on the filtered string to check for palindrome properties, which is more memory-efficient for the checking phase.
Algorithm
- Initialize an empty
StringBuilder,filteredBuilder. - Iterate through each character
cof the input strings. - If
cis an alphanumeric character, append its lowercase version tofilteredBuilder. - Initialize two pointers:
left = 0andright = filteredBuilder.length() - 1. - While
left < right: a. If the character atfilteredBuilder.charAt(left)is not equal tofilteredBuilder.charAt(right), returnfalse. b. Incrementleftand decrementright. - If the loop finishes, return
true.
Walkthrough
The initial step is identical to the previous approach: create a new StringBuilder by iterating through the input string s, and appending only the lowercase versions of alphanumeric characters. Once we have the cleaned string, we initialize two pointers: left at the beginning (index 0) and right at the end of the string. We then enter a loop that continues as long as left is less than right. Inside the loop, we compare the characters at the left and right pointers. If at any point the characters do not match, we know it's not a palindrome, and we can immediately return false. If the characters match, we move the pointers closer to the center by incrementing left and decrementing right. If the loop completes without finding any mismatches, it means the string is a palindrome, and we return true.
class Solution { public boolean isPalindrome(String s) { StringBuilder builder = new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isLetterOrDigit(c)) { builder.append(Character.toLowerCase(c)); } } String filteredString = builder.toString(); int left = 0; int right = filteredString.length() - 1; while (left < right) { if (filteredString.charAt(left) != filteredString.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
Still relatively simple to implement.
Slightly more efficient than the first approach as it avoids creating a second (reversed) string.
Cons
Still requires O(N) extra space to store the filtered string.
This is the most optimal approach. It uses two pointers, one starting from the beginning of the string and one from the end, moving towards each other. It checks for palindromic properties in-place, without creating any new strings, thus achieving constant space complexity.
Algorithm
- Initialize two pointers:
left = 0andright = s.length() - 1. - Loop while
left < right. - Inside the loop, get the characters
leftCharats[left]andrightCharats[right]. - If
leftCharis not alphanumeric, incrementleftand continue to the next iteration. - If
rightCharis not alphanumeric, decrementrightand continue to the next iteration. - If both are alphanumeric, compare their lowercase versions.
a. If
Character.toLowerCase(leftChar)is not equal toCharacter.toLowerCase(rightChar), returnfalse. - If they are equal, move the pointers inward: increment
leftand decrementright. - If the loop completes, return
true.
Walkthrough
We initialize two pointers, left at index 0 and right at the last index of the input string s. We loop as long as left is less than right. Inside the loop, we first advance the left pointer forward as long as it points to a non-alphanumeric character. Similarly, we move the right pointer backward as long as it points to a non-alphanumeric character. After these adjustments, both pointers should be pointing to alphanumeric characters (or they have crossed, ending the loop). We then compare the lowercase versions of the characters at the left and right pointers. If they are different, the string is not a palindrome, and we return false. If they are the same, we move both pointers one step closer to the center (left++, right--) and continue the process. If the loop completes, it means all corresponding alphanumeric characters matched, so the string is a palindrome, and we return true.
class Solution { public boolean isPalindrome(String s) { int left = 0; int right = s.length() - 1; while (left < right) { char leftChar = s.charAt(left); char rightChar = s.charAt(right); if (!Character.isLetterOrDigit(leftChar)) { left++; } else if (!Character.isLetterOrDigit(rightChar)) { right--; } else { if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) { return false; } left++; right--; } } return true; }}Complexity
Time
O(N)
Space
O(1)
Trade-offs
Pros
Highly efficient in terms of memory usage (O(1) space).
Performs the check in a single pass over the string.
Cons
The logic can be slightly more complex to write correctly due to the nested conditions for skipping non-alphanumeric characters.
Solutions
Solution
public class Solution { public bool IsPalindrome ( string s ) { int i = 0 , j = s . Length - 1 ; while ( i < j ) { if (! char . IsLetterOrDigit ( s [ i ])) { ++ i ; } else if (! char . IsLetterOrDigit ( s [ j ])) { -- j ; } else if ( char . ToLower ( s [ i ++]) != char . ToLower ( s [ j --])) { return false ; } } return true ; } }class Solution {public boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { if (!Character.isLetterOrDigit(s.charAt(i))) { ++i; } else if (!Character.isLetterOrDigit(s.charAt(j))) { --j; } else if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) { return false; } else { ++i; --j; } } return true; }}/** * @param {string} s * @return {boolean} */ var isPalindrome = function (s) { 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;};class Solution {public: bool isPalindrome(string s) { int i = 0, j = s.size() - 1; while (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; } } return true; }};class Solution: def isPalindrome(self, s: str) -> bool: i, j = 0, len(s) - 1 while i < j: if not s[i]. isalnum(): i += 1 elif not s[j]. isalnum(): j -= 1 elif s[i]. lower() != s[j]. lower(): return False else: i, j = i + 1, j - 1 return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.