String Palindromes

1. Introduction: The Mirror Image

A Palindrome is a string that reads the exact same forwards and backwards. "racecar", "madam", and "a" are palindromes.

Palindromes are incredibly common in coding interviews because they are mathematically perfectly symmetrical. This symmetry allows us to solve palindrome problems using elegant Two Pointer techniques or Dynamic Programming shortcuts, transforming nasty $O(N^3)$ brute-force solutions into beautiful $O(N)$ or $O(N^2)$ algorithms.

2. Core Concept: The Two Approaches

There are two primary ways to evaluate a palindrome:

1. Outside-In (Two Pointers): Place a pointer at the start 0 and the end N-1. Check if s.charAt(left) == s.charAt(right). If they match, move both pointers inward. If they cross, it's a palindrome! (Best for checking if a known string is a palindrome).
2. Inside-Out (Expand Around Center): Pick a character in the middle of the string. Expand outwards (left--, right++) as long as the characters match. (Best for finding hidden palindromes inside a larger string).

3. Beginner Code Example: Valid Palindrome

Problem Statement: (LeetCode 125) A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return true if it is a palindrome.

The Insight: Use the Outside-In Two Pointer approach. We must handle the edge cases of spaces and punctuation by actively skipping them.

public class ValidPalindrome {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) return true;
        
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            char lChar = s.charAt(left);
            char rChar = s.charAt(right);
            
            // Skip non-alphanumeric characters from the left
            if (!Character.isLetterOrDigit(lChar)) {
                left++;
            } 
            // Skip non-alphanumeric characters from the right
            else if (!Character.isLetterOrDigit(rChar)) {
                right--;
            } 
            // Compare the valid characters (converted to lowercase)
            else {
                if (Character.toLowerCase(lChar) != Character.toLowerCase(rChar)) {
                    return false; // Mismatch!
                }
                left++;
                right--;
            }
        }
        
        return true;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We make one pass through the string.
• Space Complexity: $O(1)$.

4. Intermediate Code Example: Valid Palindrome II (At Most One Deletion)

Problem Statement: (LeetCode 680) Given a string s, return true if the s can be palindrome after deleting at most one character from it.

The Insight: Start with normal Outside-In pointers. If they mismatch, you have two choices: delete the left character, or delete the right character. You must check BOTH parallel realities! If either remaining sub-string is a perfect palindrome, return true.

public class ValidPalindromeII {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // Mismatch found! Try deleting left OR try deleting right
                return isPerfectPalindrome(s, left + 1, right) || 
                       isPerfectPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        
        return true;
    }
    
    // Helper function to check strict palindrome without deletions
    private boolean isPerfectPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

5. Advanced Code Example: Longest Palindromic Substring

Problem Statement: (LeetCode 5) Given a string s, return the longest palindromic substring in s.

The Brute Force Trap: Check every single substring. $O(N^3)$. The Inside-Out Insight: A palindrome mirrors around its center. There are $2N - 1$ possible centers in a string (every character, AND the spaces between every character for even-length palindromes). If we treat every position as a center and expand outwards, we can find the longest palindrome in $O(N^2)$ time with $O(1)$ space!

public class LongestPalindrome {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        
        int start = 0;
        int end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // Case 1: Odd length palindrome (Center is 1 character)
            int len1 = expandAroundCenter(s, i, i);
            
            // Case 2: Even length palindrome (Center is BETWEEN 2 characters)
            int len2 = expandAroundCenter(s, i, i + 1);
            
            // Take the max of the two cases
            int len = Math.max(len1, len2);
            
            // If this is the longest we've found, update our start/end pointers
            if (len > end - start) {
                // Math trick to correctly calculate bounds based on the center 'i'
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        // substring in Java is (inclusive, exclusive)
        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++;
        }
        // When the loop breaks, left and right have gone ONE step too far.
        // The length is (right - left - 1)
        return right - left - 1;
    }
}

6. Common Mistakes Beginners Make

1. Using .replaceAll() to clean strings

   • The Mistake: s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
   • Why it's wrong: While this is a brilliant 1-liner in Python/JS, in Java, Regex is incredibly slow and allocates massive amounts of memory for intermediate String objects. In an interview, always use manual Character.isLetterOrDigit() with Two Pointers to demonstrate $O(1)$ space mastery.

2. Forgetting Even-Length Centers

   • The Mistake: Only expanding around i, i in Longest Palindromic Substring.
   • Why it's wrong: "abba" has a center between the two 'b's! If you only expand around single characters, you will only find odd-length palindromes and completely miss "abba". You must check i, i+1.

3. Returning right - left + 1 in Expand Around Center

   • The Mistake: return right - left + 1;
   • Why it's wrong: Look closely at the while loop. The loop breaks because the characters mismatched (or hit a boundary). This means left and right are pointing to INVALID characters! The true valid palindrome ended on the previous step. The mathematical length is right - left - 1.

7. Interview Q&A

Q1: Can Longest Palindromic Substring be solved in $O(N)$ time? Answer: Yes, using Manacher's Algorithm. It leverages previously calculated palindrome bounds to skip redundant checks. However, it is insanely complex and almost never expected in an interview unless you are explicitly applying for an elite algorithmic role. The $O(N^2)$ Expand Around Center approach is the universally accepted standard.

Q2: How do you solve "Palindromic Substrings" (LeetCode 647 - Count all palindromes)? Answer: The exact same expandAroundCenter function! Instead of tracking the max length, you simply initialize a global count = 0, and inside the while loop, you do count++ every single time the characters match. Then return the count.

Q3: Can we use Dynamic Programming for Longest Palindromic Substring? Answer: Yes. dp[i][j] is true if s.charAt(i) == s.charAt(j) AND dp[i+1][j-1] is true. It is $O(N^2)$ time and $O(N^2)$ space. However, Expand Around Center is heavily preferred because it is $O(N^2)$ time and $O(1)$ space.

8. Practice Problems

1. Valid Palindrome (LeetCode 125)
   • Goal: Master the Outside-In Two Pointer approach.
2. Valid Palindrome II (LeetCode 680)
   • Goal: Master the "Delete Left OR Delete Right" parallel checking.
3. Longest Palindromic Substring (LeetCode 5)
   • Goal: Master the Inside-Out Expand Around Center approach for both even and odd lengths.

9. Summary

• Outside-In: Validating known strings. left++, right--.
• Inside-Out: Discovering palindromes. left--, right++.
• The Core Trick: A string has $2N - 1$ centers. Always expand for (i, i) AND (i, i+1).
• Boundary Math: The length of the expanded palindrome after the loop breaks is right - left - 1.