A palindrome is a string that reads the same backward as forward (e.g., "racecar", "madam"). Palindromes are a favorite interview topic because they test your ability to handle symmetry and indices.

Think of a palindrome as a mirror image:

1. You stand in the exact middle.
2. If you look one step left and one step right, you should see the same character.
3. If you keep looking further apart, the characters should always match until you hit the edges.

---

Checking a Palindrome ($O(n)$)

The most efficient way to check if a string is a palindrome is using Two Pointers.

• Start one pointer at index 0 and another at index length - 1.
• If they don't match, it's not a palindrome.
• Move them toward each other until they meet.

Finding Palindromic Substrings

If you need to find all palindromic substrings in a string:

• Brute Force: $O(n^3)$.
• Expand Around Center: $O(n^2)$. You pick each character (and each gap between characters) as a potential center and expand outward as long as it's a palindrome.

Advanced: Manacher's Algorithm

Finding the longest palindromic substring in $O(n)$ time. This is a complex algorithm that uses information from previously found palindromes to skip work.

---

javascript Standard
/**
 * Simple Palindrome Check
 */
function isPalindrome(str) {
  // Clean the string (optional: remove non-alphanumeric)
  str = str.toLowerCase().replace(/[^a-z0-9]/g, '');
  
  let left = 0;
  let right = str.length - 1;

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

/**
 * Expand Around Center Pattern
 * Used to count total palindromic substrings.
 */
function countPalindromes(s) {
  let count = 0;

  for (let i = 0; i < s.length; i++) {
    // Odd length palindromes (single char center)
    count += expand(s, i, i);
    // Even length palindromes (gap center)
    count += expand(s, i, i + 1);
  }
  return count;
}

function expand(s, left, right) {
  let count = 0;
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    count++;
    left--;
    right++;
  }
  return count;
}

---

Top Variations

• Valid Palindrome II: Can you make it a palindrome by deleting at most one character?
• Longest Palindromic Substring: Use the "Expand Around Center" method.
• Palindromic Partitioning: Using backtracking to split a string into palindromes.

Pro-Tip

When checking palindromes, don't forget to handle case-sensitivity and spaces/punctuation unless the interviewer says otherwise. s.toLowerCase() is your friend!