Find Longest Palindrome In A String – Tech Interview Dot Org

How will you find out the longest palindrome in a given string.

💡Strategies for Solving This Problem

Understanding the Problem

A palindrome reads the same forwards and backwards. For example, "racecar" and "noon" are palindromes. We need to find the longest such substring within a given string.

Approach 1: Expand Around Center

The key insight is that every palindrome has a center. We can check all possible centers (both single characters and pairs of characters for even-length palindromes).

Key Strategies:

Two Types of Centers: Odd-length palindromes (single character) and even-length palindromes (between two characters)
Expand Outward: From each center, expand outward while characters match
Track Maximum: Keep track of the longest palindrome found so far

Approach 2: Dynamic Programming

Build a 2D table where dp[i][j] represents whether substring from index i to j is a palindrome. This is more intuitive but uses O(n²) space.

Time Complexity:

Expand Around Center: O(n²) time, O(1) space
Dynamic Programming: O(n²) time, O(n²) space
Manacher's Algorithm: O(n) time (advanced)

✅Solution

Solution: Expand Around Center

function longestPalindrome(s) {
    if (!s || s.length < 1) return "";

    let start = 0;
    let maxLength = 0;

    // Helper function to expand around center
    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        // Return length of palindrome
        return right - left - 1;
    }

    for (let i = 0; i < s.length; i++) {
        // Check for odd-length palindromes (single character center)
        let len1 = expandAroundCenter(i, i);

        // Check for even-length palindromes (pair of characters)
        let len2 = expandAroundCenter(i, i + 1);

        // Take the longer one
        let len = Math.max(len1, len2);

        // Update if we found a longer palindrome
        if (len > maxLength) {
            maxLength = len;
            // Calculate start position
            start = i - Math.floor((len - 1) / 2);
        }
    }

    return s.substring(start, start + maxLength);
}

// Test cases:
console.log(longestPalindrome("babad"));       // "bab" or "aba"
console.log(longestPalindrome("cbbd"));        // "bb"
console.log(longestPalindrome("racecar"));     // "racecar"
console.log(longestPalindrome("noon"));        // "noon"
console.log(longestPalindrome("a"));           // "a"

Alternative: Dynamic Programming Solution

function longestPalindrome(s) {
    const n = s.length;
    if (n < 2) return s;

    // dp[i][j] = true if substring from i to j is palindrome
    const dp = Array(n).fill(null).map(() => Array(n).fill(false));

    let start = 0;
    let maxLength = 1;

    // Every single character is a palindrome
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // Check for 2-character palindromes
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }

    // Check for palindromes of length 3 and greater
    for (let len = 3; len <= n; len++) {
        for (let i = 0; i < n - len + 1; i++) {
            let j = i + len - 1;

            // Check if s[i...j] is palindrome
            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                start = i;
                maxLength = len;
            }
        }
    }

    return s.substring(start, start + maxLength);
}

Complexity Analysis:

Expand Around Center:
- Time: O(n²) - we check n centers and expand up to n times
- Space: O(1) - only using a few variables
Dynamic Programming:
- Time: O(n²) - filling n² table entries
- Space: O(n²) - storing the DP table

Recommendation: Use expand-around-center for better space efficiency unless you need to query multiple palindrome checks.