Longest Palindromic Subsstring

5.Longest Palindromic Substring

String

Dynamic Programming

Problem Statement:

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

Example:

Input:

s = "babad"

→

Output:

"bab"

Algorithm:

1. Create DP table for substring states
2. Check palindromes of increasing length
3. Track max length and starting index
4. Return substring using tracked values

Complexity:

Time: O(n²) | Space: O(n²)

Java Solution:

//DP Method
public String longestPalindrome(String s) {
    int n = s.length();
    int maxLen = 0;  // Track length of longest palindrome
    int index = 0;   // Track start index of longest palindrome
    
    // dp[i][j] represents if substring(i,j) is palindrome
    boolean[][] dp = new boolean[n][n];
       
    // Check all possible lengths
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {  // Matching chars at ends
                if (len == 1 || len == 2 || dp[i + 1][j - 1]) {  // Check if inner substring is palindrome
                    dp[i][j] = true;
                    maxLen = len;
                    index = i;
                }
            }
        }
    }
    
    return s.substring(index, index + maxLen);
}

Python Solution:

def longestPalindrome(self, s: str) -> str:
    n = len(s)
    maxLen = 0
    index = 0
    
    # Initialize DP table
    dp = [[False] * n for _ in range(n)]
    
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j] and (length <= 2 or dp[i+1][j-1]):
                dp[i][j] = True
                if length > maxLen:
                    maxLen = length
                    index = i
                    
    return s[index:index + maxLen]

C++ Solution:

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        int maxLen = 0;
        int index = 0;
        
        // Initialize DP table
        vectorbool>> dp(n, vector<bool>(n, false));
        
        for(int len = 1; len <= n; len++) {
            for(int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                if(s[i] == s[j] && (len <= 2 || dp[i+1][j-1])) {
                    dp[i][j] = true;
                    if(len > maxLen) {
                        maxLen = len;
                        index = i;
                    }
                }
            }
        }
        
        return s.substr(index, maxLen);
    }
};