LeetCode Solution 125 - Valid Palindrome

Problem Statement

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

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.

---

Optimal Approach: Two Pointers

Why Two Pointers?

• Efficiently checks characters from both ends.
• Ignores non-alphanumeric characters.
• Works in O(N) time with O(1) extra space.

Algorithm:

1. Use two pointers: left at the start and right at the end.
2. Skip non-alphanumeric characters.
3. Convert characters to lowercase before comparison.
4. If characters don’t match, return false.
5. Move pointers inward until they meet.
6. If no mismatches are found, return true.

---

C++ Code Implementation

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !isalnum(s[left])) left++;
            while (left < right && !isalnum(s[right])) right--;
            
            if (tolower(s[left]) != tolower(s[right])) return false;
            left++, right--;
        }
        return true;
    }
};

---

Step-by-Step Explanation

1. Initialize Two Pointers: left starts at 0, right starts at s.length() - 1.
2. Skip Non-Alphanumeric Characters:
   • If s[left] is not alphanumeric, increment left.
   • If s[right] is not alphanumeric, decrement right.
3. Compare Characters:
   • Convert s[left] and s[right] to lowercase.
   • If they do not match, return false.
4. Move Pointers:
   • Increment left and decrement right.
5. Return True if No Mismatches.

---

Dry Run

Input:

s = "A man, a plan, a canal: Panama"

Execution:

Step	Left Pointer	Right Pointer	Characters	Comparison	Result
1	A (0)	a (29)	A == a	✅	Continue
2	m (1)	m (28)	m == m	✅	Continue
3	a (2)	a (27)	a == a	✅	Continue
...	...	...	...	...	...
Final	Pointers Meet	✅	"Palindrome"	✅	✅

---

Alternative Approaches

Approach	Time Complexity	Space Complexity	Reason for Rejection
Brute Force (Reverse & Compare)	O(N)	O(N)	Uses extra space for reversed string
Stack-Based Approach	O(N)	O(N)	Unnecessary stack usage
Two Pointers (Best)	O(N)	O(1)	Most efficient

---

Complexity Analysis

• Time Complexity: O(N) since each character is checked at most once.
• Space Complexity: O(1) since only pointers are used.

---

Conclusion

• Best Approach: Two Pointers.
• Further Practice:
  • Valid Palindrome II
  • Longest Palindromic Substring

This solution efficiently checks if a string is a valid palindrome using Two Pointers, making it optimal for large inputs.