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. It should handle strings such as "aba" (valid palindrome) and "Aba" (invalid palindrome)
Sample Test Case
Input: "Aba"
Output: true
Input: "abc"
Output: false
Input: "121"
Output: true
Input: "123"
Output: false
Approaches
Brute Force Approach
Idea
The brute force method involves reversing the string. If the reversed string is the same as the original string, it is a palindrome.
Steps
- Reverse the original string.
- Compare the reversed string with the original string.
- Return
true if both are the same, otherwise return false.
Time Complexity
- O(n) for reversing the string and O(n) for storing the reversed array, where
n is the length of the string.
- Total: O(n).
Space Complexity
- O(n) for storing the reversed string.
- Total: O(n).
Example Code
Dry Run
For the input "Aba":
- After cleaning:
"aba"
- After reversing:
"aba"
- 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:
- Compare the characters at
left and right.
- if both are equal then increment left and right pointer
- if any one of then are not equal then return false
- if the loop ends without returning then return true
- 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 "Aba":
left = 0, right = 2 → compare A with a → match.- Both pointers move inward, and since there are no mismatches, return
true.
Example Test Cases
Test Case 1
Input: "abc"
Output: false
Test Case 2
Input: "aba"
Output: true
Test Case 3
Input: "Aba"
Output: true
Test Case 4
Input: "121"
Output: true
Test Case 5
Input: "123"
Output: false
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.