Palindrome Problems

A Palindrome is a string that reads the same forward and backward. Common examples include “racecar”, “level”, and “madam”.

In DSA interviews, palindrome problems frequently test your ability to manipulate indices using the Two Pointer technique.

1. Problem: Valid Palindrome

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

Example:

• Input: s = "A man, a plan, a canal: Panama"
• Output: true (“amanaplanacanalpanama” is a palindrome)

Strategy: Two Pointers (Inward)

We initialize two pointers: left at the start (0) and right at the end (s.length - 1). We move them towards each other, skipping non-alphanumeric characters. If at any point s[left] ≠ s[right], it’s not a palindrome.

public boolean isPalindrome(String s) {
  if (s.isEmpty()) return true;
  int left = 0;
  int right = s.length() - 1;

  while (left < right) {
    // Move left forward until alphanumeric
    while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
      left++;
    }
    // Move right backward until alphanumeric
    while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
      right--;
    }

    // Check for mismatch (case-insensitive)
    if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
      return false;
    }

    left++;
    right--;
  }
  return true;
}

2. Problem: Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s.

Example:

• Input: s = "babad"
• Output: "bab" (or “aba”)

Strategy: Expand Around Center

A palindrome mirrors around its center. Therefore, a palindrome of length N has a center.

• “aba” has center ‘b’.
• “abba” has center between ‘b’ and ‘b’.

For every index i in the string, we can treat it as the center and try to expand outwards as long as the characters match. There are 2N - 1 centers (N single-character centers + N-1 effective centers between characters).

Visualization: The Expansion

Center: -

Current Palindrome:

Max Palindrome:

Implementation

public String longestPalindrome(String s) {
  if (s == null || s.length() < 1) return "";
  int start = 0, end = 0;

  for (int i = 0; i < s.length(); i++) {
    // Expand for odd length (center is i)
    int len1 = expandAroundCenter(s, i, i);
    // Expand for even length (center is between i and i+1)
    int len2 = expandAroundCenter(s, i, i + 1);

    int len = Math.max(len1, len2);
    if (len > end - start) {
      start = i - (len - 1) / 2;
      end = i + len / 2;
    }
  }
  return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
  while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
    left--;
    right++;
  }
  // Perform calculation to return length: (right - 1) - (left + 1) + 1 = right - left - 1
  return right - left - 1;
}

Practice Problems

1. Valid Palindrome II (Easy) - Use two pointers, allow deleting 1 char.
2. Palindromic Substrings (Medium) - Count total number of palindromes.
3. Longest Palindromic Subsequence (Medium) - Using DP (different technique!).

3. Deep Dive Strategy Lab: Palindrome Problems

Intuition Through Analogy

Think of this chapter like searching text in a large log stream. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?