Palindromes

Concept

A Palindrome is a string that reads the exact same forwards and backwards.

• Valid: racecar, madam, a
• Invalid: apple, hello

Palindrome problems are an industry-standard way to test your ability to implement the Two Pointers (Meet in the Middle) technique.

Valid Palindrome

Problem: Given a string, determine if it is a palindrome, ignoring non-alphanumeric characters and case.
(e.g., “A man, a plan, a canal: Panama” -> true)

The $O(N)$ Space Approach (Bad):
s.replace(/[^A-Za-z0-9]/g, '').toLowerCase().split('').reverse().join('') === s
This creates multiple brand new strings and arrays in memory. If the string is 100MB, you just crashed the browser.

The $O(1)$ Space Approach (Optimal):
Use Two Pointers. Squeeze inward. Skip any characters that aren’t letters or numbers.

function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
    
    // Helper function (often written as a Regex test in JS)
    const isAlphanumeric = (c: string) => /^[a-z0-9]+$/i.test(c);

    while (left < right) {
        // Skip junk characters on the left
        while (left < right && !isAlphanumeric(s[left])) {
            left++;
        }
        // Skip junk characters on the right
        while (left < right && !isAlphanumeric(s[right])) {
            right--;
        }
        
        // Compare the valid characters
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        
        left++;
        right--;
    }
    
    return true;
}

Palindrome Permutation

Problem: Given a string, can you rearrange the letters to form a palindrome?
(e.g., ivicc -> true, because it can become civic).

You cannot use Two Pointers here because the string is scrambled. You must use a Frequency Counter (Hash Set) to check the mathematical properties of a palindrome.

The Math of a Palindrome:
To build a palindrome, every single character must have a “partner” on the opposite side of the string.
Therefore, all characters must have an EVEN frequency.
The only exception is the absolute middle character (like the ‘e’ in ‘racecar’), which means you are allowed to have exactly ONE character with an ODD frequency.

function canFormPalindrome(s: string): boolean {
    const odds = new Set<string>();
    
    for (let char of s) {
        if (odds.has(char)) {
            // We found its partner! The count is now even. Remove it.
            odds.delete(char);
        } else {
            // First time seeing it, count is odd. Add it.
            odds.add(char);
        }
    }
    
    // If there is 1 or 0 odd characters left, it can be a palindrome!
    return odds.size <= 1;
}

Interview Questions

Q: A problem asks you to find the “Longest Palindromic Substring” inside a massive string (e.g., babad -> bab or aba). If you check every possible substring and run the isPalindrome Two-Pointer check on it, what is the time complexity?
A: Checking every possible substring requires a double for loop to generate the start and end boundaries ($O(N^2)$). Then, running the isPalindrome check on each substring takes $O(N)$ time. The total complexity is a terrible $O(N^3)$.

Q: How do you optimize the Longest Palindromic Substring problem down to $O(N^2)$?
A: You invert the logic. Instead of starting at the outside edges and squeezing inward to check if it’s a palindrome, you start at the middle and expand outward to build the palindrome.
You loop through every character in the string, treating it as the “center” of a potential palindrome. You initialize two pointers at that center (left = i, right = i), and aggressively step them outward (left--, right++) as long as the characters match. (You must do this twice for every character: once assuming an odd-length palindrome center, and once assuming an even-length center left = i, right = i+1). This evaluates everything in exactly $O(N^2)$ time.