125. Valid Palindrome - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. In other words, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, the string should read the same forward and backward.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true
Explanation:
After cleaning, the string becomes "amanaplanacanalpanama", which is a palindrome.

Example 2:

Input: "race a car"
Output: false
Explanation:
After cleaning, the string becomes "raceacar", which is not a palindrome.

Constraints:

s consists of printable ASCII characters.
The length of s is at least 1.

Intuition and Hints

Filtering Non-Alphanumeric Characters:
Since we only care about letters and digits, any spaces, punctuation, or other symbols must be ignored.
Case Insensitivity:
To simplify comparisons, convert all letters to the same case (lowercase is common).
Two Approaches:
1. Two-Pointer Approach:
  Use two pointers (one starting at the beginning and one at the end) to compare corresponding characters while skipping non-alphanumeric characters.
2. Filter and Compare Approach:
  First, create a new string containing only the lowercase alphanumeric characters, then check if this string is the same as its reverse.

Approaches

Approach 1: Two-Pointer Technique

Explanation:

Initialization:
Set two pointers—left at the beginning of the string and right at the end.
Skip Non-Alphanumeric Characters:
Increment the left pointer and decrement the right pointer as long as they point to characters that are not alphanumeric.
Comparison:
Compare the characters at the left and right positions (after converting them to lowercase). If they differ, the string is not a palindrome.
Advance Pointers:
Continue moving the pointers toward the center until they meet or cross.
Return:
If all corresponding characters match, return true.

Python Code (Two-Pointer Approach):

Python3

. . . .

Java Code (Two-Pointer Approach):

Java

. . . .

Approach 2: Filter and Compare

Explanation:

Filter:
Traverse the string and construct a new string that contains only the lowercase alphanumeric characters.
Compare:
Check if the filtered string is equal to its reverse. If it is, then the original string is a palindrome.

Python Code (Filter and Compare Approach):

Python3

. . . .

Java Code (Filter and Compare Approach):

Java

. . . .

Complexity Analysis

Two-Pointer Approach:
- Time Complexity: O(n), where n is the length of the string.
- Space Complexity: O(1) (ignoring the input string and considering only extra pointers and variables).
Filter and Compare Approach:
- Time Complexity: O(n) for filtering and O(n) for reversing the string, so overall O(n).
- Space Complexity: O(n) due to the extra storage for the filtered string.

Common Pitfalls & Edge Cases

Non-Alphanumeric Characters:
Ensure that all characters that are not letters or digits are ignored.
Case Insensitivity:
Always convert characters to the same case (lowercase is typical) before comparing.
Empty String:
An empty string is considered a palindrome.
Single Character Strings:
A string with one alphanumeric character is trivially a palindrome.