Given a string s, check whether it is a valid palindrome.
A valid palindrome reads the same forward and backward after converting all uppercase letters to lowercase and removing all non-alphanumeric characters.
Alphanumeric characters include letters and digits.
Return true if the string is a valid palindrome, otherwise return false.
Example 1
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes "amanaplanacanalpanama", which is a palindrome.
Example 2
Input: s = "race a car"
Output: false
Explanation: After cleaning the string, it becomes "raceacar", which is not a palindrome.
Brute Force Approach
Spaces, punctuation marks, and letter case should not affect palindrome validation. Building a cleaned string first creates the exact sequence required for comparison.
Reversing the cleaned string provides a direct palindrome check. Equal forward and reversed sequences confirm a palindrome, while unequal sequences reveal a mismatch. Two additional strings make the method simple but increase auxiliary space.
Algorithm
Initialize an empty string cleaned for storing lowercase alphanumeric characters.
Traverse s from left to right, append every alphanumeric character to cleaned after lowercase conversion, and ignore all remaining characters.
Create reversedString as a copy of cleaned so the normalized sequence remains available for direct comparison.
Reverse reversedString to build the backward character sequence.
Compare cleaned with reversedString and return true when both strings match; otherwise, return false.
Dry Run
Valid Palindrome Brute Force Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Checks whether a character is alphanumeric. Letters from a-z, A-Z, and digits from 0-9 are considered valid. */ bool isAlphaNumeric(char ch) { return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'); } /* Converts an uppercase character to lowercase. Digits and lowercase letters are returned unchanged. */ char toLowerChar(char ch) { if(ch >= 'A' && ch <= 'Z') { return char(ch + 32); } return ch; } /* Checks palindrome by creating a cleaned string and comparing it with its reversed version. */ bool isPalindrome(string s) { string cleaned = ""; // Build the cleaned string using only lowercase alphanumeric characters for(char ch : s) { if(isAlphaNumeric(ch)) { cleaned += toLowerChar(ch); } } string reversedString = cleaned; reverse(reversedString.begin(), reversedString.end()); return cleaned == reversedString; }};/* Driver function used to test the brute force approach.*/int main() { string s = "A man, a plan, a canal: Panama"; Solution obj; bool ans = obj.isPalindrome(s); cout << (ans ? "true" : "false"); return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the length of s. One traversal creates cleaned, one copy creates reversedString, and one reversal and comparison process at most N characters.
Space Complexity: O(N), because cleaned and reversedString store normalized character sequences.
Better Approach
A reversed copy becomes unnecessary after the cleaned string has been created. Palindrome symmetry can be checked by comparing opposite characters inside cleaned.
A left pointer begins at the first character, while a right pointer begins at the final character. Matching pairs allow inward movement, while the first mismatch confirms an invalid palindrome.
Algorithm
Initialize cleaned and append every lowercase alphanumeric character from s while ignoring spaces, punctuation, and symbols.
Initialize left with 0 and right with
cleaned.length - 1to represent opposite ends of the normalized sequence.Compare
cleaned[left]withcleaned[right]while left remains smaller than right.Return false immediately after finding unequal characters because palindrome symmetry has failed.
Increment left and decrement right after every matching pair.
Return true after all opposite pairs match.
Dry Run
Valid Palindrome Better Approach Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Checks whether a character is alphanumeric. Letters from a-z, A-Z, and digits from 0-9 are considered valid. */ bool isAlphaNumeric(char ch) { return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'); } /* Converts an uppercase character to lowercase. Digits and lowercase letters are returned unchanged. */ char toLowerChar(char ch) { if(ch >= 'A' && ch <= 'Z') { return char(ch + 32); } return ch; } /* Checks palindrome by cleaning the string first, then comparing characters from both ends. */ bool isPalindrome(string s) { string cleaned = ""; // Build the cleaned string using only lowercase alphanumeric characters for(char ch : s) { if(isAlphaNumeric(ch)) { cleaned += toLowerChar(ch); } } int left = 0; int right = cleaned.size() - 1; // Compare opposite characters of the cleaned string while(left < right) { if(cleaned[left] != cleaned[right]) { return false; } left++; right--; } return true; }};/* Driver function used to test the better approach.*/int main() { string s = "A man, a plan, a canal: Panama"; Solution obj; bool ans = obj.isPalindrome(s); cout << (ans ? "true" : "false"); return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the length of s. One traversal creates cleaned, and one two-pointer traversal checks the normalized sequence.
Space Complexity: O(N), because cleaned stores all retained characters.
Optimal Approach
A separate cleaned string is not required. Two pointers can process the original string directly while skipping characters excluded from palindrome comparison.
The left pointer searches forward for the next alphanumeric character, while the right pointer searches backward for the previous alphanumeric character. Lowercase comparison of valid characters confirms or rejects each symmetric pair using constant auxiliary space.
Algorithm
Initialize left with 0 and right with
s.length - 1to begin comparison from opposite ends.Move left forward while left remains smaller than right and
s[left]is non-alphanumeric.Move right backward while left remains smaller than right and
s[right]is non-alphanumeric.Convert both selected characters to lowercase and return false when the normalized characters differ.
Increment left and decrement right after every matching pair.
Return true after the pointers meet or cross without any mismatch.
Dry Run
Valid Palindrome Optimal Approach Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Checks whether a character is alphanumeric. Letters from a-z, A-Z, and digits from 0-9 are considered valid. */ bool isAlphaNumeric(char ch) { return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'); } /* Converts an uppercase character to lowercase. Digits and lowercase letters are returned unchanged. */ char toLowerChar(char ch) { if(ch >= 'A' && ch <= 'Z') { return char(ch + 32); } return ch; } /* Checks palindrome directly on the original string using two pointers. Non-alphanumeric characters are skipped during comparison. */ bool isPalindrome(string s) { int left = 0; int right = s.size() - 1; while(left < right) { // Skip non-alphanumeric characters from the left side while(left < right && !isAlphaNumeric(s[left])) { left++; } // Skip non-alphanumeric characters from the right side while(left < right && !isAlphaNumeric(s[right])) { right--; } // Valid characters are compared after converting to lowercase if(toLowerChar(s[left]) != toLowerChar(s[right])) { return false; } left++; right--; } return true; }};/* Driver function used to test the optimal approach.*/int main() { string s = "A man, a plan, a canal: Panama"; Solution obj; bool ans = obj.isPalindrome(s); cout << (ans ? "true" : "false"); return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the length of s. Both pointers move only toward the centre, so every character is processed at most once.
Space Complexity: O(1), because only two pointers and temporary character values require auxiliary storage.
FAQS
Q1. Why are digits included during palindrome validation?
Digits belong to the alphanumeric character set. A string such as "1a2a1" therefore qualifies as a valid palindrome.
Q2. Why does a string containing only punctuation return true?
Normalization removes every character, producing an empty sequence. An empty sequence reads identically from both directions.
Q3. Can the optimal approach modify the original string?
No modification is required. Two pointers read valid characters directly from s and compare normalized values.
Q4. How should character classification be handled safely in C++?
Functions such as isalnum and tolower should receive values converted to unsigned char, preventing undefined behaviour for negative signed-character values.
Q5. How does Unicode support affect the implementation?
Standard ASCII-based helpers correctly process English letters and digits. Full Unicode support requires Unicode-aware character classification and case-folding utilities.
Be the first to add a comment.