Problem Statement
Given a string, check if it is a valid palindrome. A string is considered a palindrome if it reads the same forward and backward after converting all uppercase letters to lowercase and ignoring all non-alphanumeric characters.
Sample Test Case
Input: "A man, a plan, a canal: Panama"
Output: true
Approaches
Brute Force Approach
Idea
The brute force method involves reversing the string after removing all non-alphanumeric characters and converting everything to lowercase. If the reversed string is the same as the original cleaned string, it is a palindrome.
Steps
- Remove non-alphanumeric characters from the string.
- Convert all characters to lowercase.
- Reverse the cleaned string.
- Compare the reversed string with the cleaned string.
- Return
true if both are the same, otherwise return false.
Time Complexity
- O(n) for cleaning the string and O(n) for reversing, where
n is the length of the string.
- Total: O(n).
Space Complexity
- O(n) for storing the cleaned string and the reversed string.
- Total: O(n).
Example Code
Dry Run
For the input "A man, a plan, a canal: Panama":
- After cleaning:
"amanaplanacanalpanama"
- After reversing:
"amanaplanacanalpanama"
- Since both are the same, return
true.
Efficient Approach (Two-Pointer Technique)
Idea
The two-pointer approach compares characters from the beginning and end of the string, moving inward, while skipping non-alphanumeric characters. This approach avoids creating a new reversed string, improving space efficiency.
Steps
- Initialize two pointers:
left at the start and right at the end of the string.
- Move both pointers towards each other:
- Skip non-alphanumeric characters.
- Compare the characters at
left and right after converting them to lowercase.
- If all characters match, return
true. If any characters mismatch, return false.
Time Complexity
- O(n), where
n is the length of the string.
Space Complexity
- O(1) for using only pointers without additional space.
Example Code
Dry Run
For the input "A man, a plan, a canal: Panama":
left = 0, right = 29 → compare A with a → match.- Continue inward, skipping non-alphanumeric characters and matching
m, a, n, and so on.
- Eventually, all characters match, so return
true.
Example Test Case
Test Case 1
Input: "race a car"
Output: false
Test Case 2
Input: " "
Output: true (Empty or whitespace strings are considered palindromes.)
Test Case 3
Input: "Able , was I saw eLba"
Output: true
Complexity Analysis
Brute Force Approach
- Time Complexity: O(n), where
n is the length of the string.
- Space Complexity: O(n), as additional space is used for the cleaned and reversed string.
Efficient (Two-Pointer) Approach
- Time Complexity: O(n), where
n is the length of the string.
- Space Complexity: O(1), as no additional space is used apart from the two pointers.
Conclusion
The brute force approach works but uses additional space to store the cleaned and reversed string. The two-pointer approach is more efficient in terms of space complexity, achieving O(1) space while still maintaining O(n) time complexity.