Palindrome Check

Palindrome Check

A Palindrome is a word, phrase, number, or other sequence of characters that reads the same backward as forward (ignoring spaces, punctuation, and capitalization). Classic examples include "racecar", "madam", and "radar".

Implementation Mechanics: The Two Pointers Technique

Checking for a palindrome is highly optimized using the Two Pointers pattern, which scans from both ends inward:

1. Pointers Placement: Place a left pointer at index 0 (start of string) and a right pointer at index N - 1 (end of string).
2. Comparison: Compare the characters at arr[left] and arr[right].
   • If they do not match, the string is not a palindrome. Stop and return false.
   • If they match, increment left (left++) and decrement right (right--).
3. Loop: Repeat step 2 as long as left < right.
4. Success: If the pointers meet or cross without any mismatch, return true.

Complexity Analysis

• Time Complexity:
  • Best Case: O(1) (if the very first and last characters do not match, e.g., "apple")
  • Average/Worst Case: O(N) (where N is the length of the string, since we make at most N / 2 comparisons)
• Space Complexity: O(1) (constant auxiliary space as the verification is done entirely in-place)