Palindrome Check

Tags

Palindrome Check

Category

Strings

Difficulty

Easy

Problem Statement

Given a string, determine whether it is a palindrome. A palindrome is a string that reads the same forward and backward. The check is typically case-sensitive and considers every character in the string.

Intuition

A palindrome is symmetric around its center. Instead of reversing the entire string and comparing, we can compare characters from the outside inward. If every pair of characters equidistant from the center matches, the string is a palindrome. This two-pointer approach avoids creating a new string and checks the property directly.

Approach

  1. Initialize two pointers: one at the start of the string (left = 0) and one at the end (right = length - 1).
  2. While left < right:
    • If the character at left does not equal the character at right, return false.
    • Increment left and decrement right.
  3. If the loop completes without finding a mismatch, return true.

Pseudocode

function isPalindrome(string):
    left = 0
    right = length(string) - 1

    while left < right:
        if string[left] != string[right]:
            return false
        left = left + 1
        right = right - 1

    return true

Time & Space Complexity

  • Time: O(n) where n is the length of the string. Each character is visited at most once.
  • Space: O(1). Only two pointer variables are used regardless of input size.

Key Insights

  • The two-pointer technique is the optimal approach, avoiding the O(n) space cost of creating a reversed copy.
  • A single character or an empty string is always a palindrome.
  • A recursive approach (comparing first and last characters, then recursing on the substring) works but uses O(n) space on the call stack.

Edge Cases

  • Empty string: should return true (vacuously a palindrome).
  • Single character string: should return true.
  • String with all identical characters (e.g., "aaaa"): should return true.
  • Even-length vs. odd-length strings: the algorithm handles both naturally since the pointers meet or cross at the center.
  • Strings with spaces or special characters: depending on problem constraints, you may need to preprocess or skip non-alphanumeric characters.

Linked mentions