Valid Palindrome: Checking Symmetry in Strings

The "Valid Palindrome" problem focuses on determining whether a given string is a palindrome. A palindrome is a sequence of characters that reads the same forward and backward, typically ignoring spaces, punctuation, and capitalization.

Problem Statement

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

Example

• Input: "A man, a plan, a canal: Panama"
• Output: true
• Input: "race a car"
• Output: false

Solution Approach - Two Pointers Technique (typescript)

function isPalindrome(s: string): boolean {
  s = s.replace(/[^A-Za-z0-9]/g, "").toLowerCase();
  let left = 0,
    right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
}

Breaking Down the Solution

• Preprocessing: Remove all non-alphanumeric characters and convert to lowercase to standardize the string.
• Two Pointers: Use two pointers, one at the start and one at the end, moving towards the center.
• Compare Characters: If characters at the start and end pointers don't match, it's not a palindrome.
• Iterate and Validate: Continue moving pointers inward and comparing until they meet or a mismatch is found.

Conclusion

The Valid Palindrome problem is a classic example of using the two pointers technique to check for symmetry in strings. It's a fundamental exercise in string manipulation and pattern recognition.