Longest Palindromic Substring

Find the longest palindromic substring in a given string

Language Selection

Choose your preferred programming language

Showing: Python

Longest Palindromic Substring

Problem Statement

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

Input/Output Specifications

Input: A string s where 1 <= s.length <= 1000 and s consists of only digits and English letters
Output: The longest palindromic substring

Constraints

1 <= s.length <= 1000
s consists of only digits and English letters

Examples

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Solution Approaches

Approach 1: Expand Around Centers - Optimal

Algorithm Explanation:

For each possible center, expand outward to find the longest palindrome
Handle both odd-length (center at character) and even-length (center between characters) palindromes
Keep track of the longest palindrome found

Implementation:

Python:

def longestPalindrome(s):
    """
    Find longest palindromic substring using expand around centers
    Time: O(n^2)
    Space: O(1)
    """
    if not s:
        return ""
    
    start = 0
    max_len = 1
    
    for i in range(len(s)):
        # Check for odd-length palindromes (center at i)
        len1 = expandAroundCenter(s, i, i)
        
        # Check for even-length palindromes (center between i and i+1)
        len2 = expandAroundCenter(s, i, i + 1)
        
        # Get the maximum length
        current_max = max(len1, len2)
        
        # Update if we found a longer palindrome
        if current_max > max_len:
            max_len = current_max
            start = i - (current_max - 1) // 2
    
    return s[start:start + max_len]

def expandAroundCenter(s, left, right):
    """Expand around center and return length of palindrome"""
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    
    return right - left - 1

Java:

class Solution {
    /**
     * Find longest palindromic substring using expand around centers
     * Time: O(n^2)
     * Space: O(1)
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        
        int start = 0;
        int maxLen = 1;
        
        for (int i = 0; i < s.length(); i++) {
            // Check for odd-length palindromes (center at i)
            int len1 = expandAroundCenter(s, i, i);
            
            // Check for even-length palindromes (center between i and i+1)
            int len2 = expandAroundCenter(s, i, i + 1);
            
            // Get the maximum length
            int currentMax = Math.max(len1, len2);
            
            // Update if we found a longer palindrome
            if (currentMax > maxLen) {
                maxLen = currentMax;
                start = i - (currentMax - 1) / 2;
            }
        }
        
        return s.substring(start, start + maxLen);
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Go:

func longestPalindrome(s string) string {
    /**
     * Find longest palindromic substring using expand around centers
     * Time: O(n^2)
     * Space: O(1)
     */
    if len(s) == 0 {
        return ""
    }
    
    start := 0
    maxLen := 1
    
    for i := 0; i < len(s); i++ {
        // Check for odd-length palindromes (center at i)
        len1 := expandAroundCenter(s, i, i)
        
        // Check for even-length palindromes (center between i and i+1)
        len2 := expandAroundCenter(s, i, i+1)
        
        // Get the maximum length
        currentMax := len1
        if len2 > len1 {
            currentMax = len2
        }
        
        // Update if we found a longer palindrome
        if currentMax > maxLen {
            maxLen = currentMax
            start = i - (currentMax-1)/2
        }
    }
    
    return s[start : start+maxLen]
}

func expandAroundCenter(s string, left, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}

JavaScript:

/**
 * Find longest palindromic substring using expand around centers
 * Time: O(n^2)
 * Space: O(1)
 */
function longestPalindrome(s) {
    if (!s || s.length === 0) {
        return "";
    }
    
    let start = 0;
    let maxLen = 1;
    
    for (let i = 0; i < s.length; i++) {
        // Check for odd-length palindromes (center at i)
        const len1 = expandAroundCenter(s, i, i);
        
        // Check for even-length palindromes (center between i and i+1)
        const len2 = expandAroundCenter(s, i, i + 1);
        
        // Get the maximum length
        const currentMax = Math.max(len1, len2);
        
        // Update if we found a longer palindrome
        if (currentMax > maxLen) {
            maxLen = currentMax;
            start = i - Math.floor((currentMax - 1) / 2);
        }
    }
    
    return s.substring(start, start + maxLen);
}

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

C#:

public class Solution {
    /// <summary>
    /// Find longest palindromic substring using expand around centers
    /// Time: O(n^2)
    /// Space: O(1)
    /// </summary>
    public string LongestPalindrome(string s) {
        if (string.IsNullOrEmpty(s)) {
            return "";
        }
        
        int start = 0;
        int maxLen = 1;
        
        for (int i = 0; i < s.Length; i++) {
            // Check for odd-length palindromes (center at i)
            int len1 = ExpandAroundCenter(s, i, i);
            
            // Check for even-length palindromes (center between i and i+1)
            int len2 = ExpandAroundCenter(s, i, i + 1);
            
            // Get the maximum length
            int currentMax = Math.Max(len1, len2);
            
            // Update if we found a longer palindrome
            if (currentMax > maxLen) {
                maxLen = currentMax;
                start = i - (currentMax - 1) / 2;
            }
        }
        
        return s.Substring(start, maxLen);
    }
    
    private int ExpandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

Complexity Analysis:

Time Complexity: O(n^2) - For each center, expand outward
Space Complexity: O(1) - Only using constant extra space

Approach 2: Dynamic Programming

Algorithm Explanation:

Create a 2D DP table where dp[i][j] represents if s[i:j] is a palindrome
Fill the table for all substrings
Keep track of the longest palindrome found

Implementation:

Python:

def longestPalindrome_dp(s):
    """
    Find longest palindromic substring using dynamic programming
    Time: O(n^2)
    Space: O(n^2)
    """
    if not s:
        return ""
    
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1
    
    # Every single character is a palindrome
    for i in range(n):
        dp[i][i] = True
    
    # Check for palindromes of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2
    
    # Check for palindromes of length 3 and more
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start = i
                max_len = length
    
    return s[start:start + max_len]

Complexity Analysis:

Time Complexity: O(n^2) - Fill the DP table
Space Complexity: O(n^2) - DP table storage

Key Insights

Expand Around Centers: Check each possible center for palindromes
Odd and Even Lengths: Handle both odd and even-length palindromes
Two Pointers: Use two pointers to expand outward from center
Optimization: Expand around centers is more space-efficient than DP

Edge Cases

Empty String: Return empty string
Single Character: Return the character itself
No Palindrome: Return the first character
All Same Characters: Return the entire string
Two Characters: Handle the two-character case

Test Cases

def test_longestPalindrome():
    # Test case 1
    assert longestPalindrome("babad") == "bab"
    
    # Test case 2
    assert longestPalindrome("cbbd") == "bb"
    
    # Test case 3
    assert longestPalindrome("a") == "a"
    
    # Test case 4
    assert longestPalindrome("ac") == "a"
    
    # Test case 5
    assert longestPalindrome("racecar") == "racecar"
    
    # Test case 6
    assert longestPalindrome("abcdef") == "a"
    
    print("All tests passed!")

test_longestPalindrome()

Follow-up Questions

Longest Palindromic Subsequence: Find longest palindromic subsequence?
Count Palindromes: Count all palindromic substrings?
Palindrome Partitioning: Partition string into palindromes?
Valid Palindrome: Check if string is a palindrome?
Shortest Palindrome: Make string a palindrome with minimum additions?

Common Mistakes

Center Calculation: Incorrect calculation of palindrome center
Boundary Conditions: Not handling string boundaries correctly
Length Calculation: Wrong calculation of palindrome length
Index Management: Off-by-one errors in index calculations
Edge Case Handling: Not handling single character or empty string

Interview Tips

Start with Brute Force: Show understanding of the problem
Optimize with Expand Around Centers: Explain the optimal approach
Handle Both Cases: Mention odd and even-length palindromes
Discuss Trade-offs: Compare different approaches
Code Carefully: Pay attention to index calculations

Concept Explanations

Palindrome: A string that reads the same backward as forward. Examples include “racecar”, “level”, and “madam”.

Expand Around Centers: A technique where we consider each character (and position between characters) as a potential center of a palindrome and expand outward to find the longest palindrome.

Two Pointers Technique: Using two pointers that move in opposite directions to check for palindromic properties.

When to Use: Use this pattern when you need to find palindromic substrings, check for palindromes, or solve related string problems involving symmetry.