Longest Palindromic Substring

93.Longest Palindromic Substring

String

Dynamic Programming

Problem Statement:

Given a string s, return the longest palindromic substring in s. A palindrome is a string that reads the same backward as forward.

Algorithm:

1. Use a 2D dynamic programming (DP) table to track whether substrings are palindromes:
• dp[i][j] is 1 if the substring from index i to j is a palindrome, otherwise 0.
• Single-character substrings are always palindromes.
• Two-character substrings are palindromes if the characters match.
• For substrings of length greater than 2, check if the first and last characters match and the inner substring is a palindrome.
2. Iterate through all ending indices j and starting indices i to fill the DP table.
3. Track the starting index and length of the longest palindrome to extract the result.

Complexity:

Time: O(n²), where n is the length of the string | Space: O(n²) for the DP table.

Java Implementation:

public class Solution {
    public String longestPalindrome(String s) {
        int[][] dp = new int[s.length()][s.length()]; // DP table
        int start = 0, maxLength = 1; // Track the start and max length of the palindrome

        // Iterate over all ending indices j
        for (int j = 0; j < s.length(); j++) {
            // Iterate over all starting indices i <= j
            for (int i = j; i >= 0; i--) {
                // Check if characters match and form a palindrome
                if (s.charAt(i) == s.charAt(j)) {
                    // Single-character, two-character, or valid inner substring
                    if (j - i == 1 || i == j || dp[i + 1][j - 1] == 1) {
                        dp[i][j] = 1; // Mark as a palindrome
                        // Update the longest palindrome if needed
                        if (j - i + 1 > maxLength) {
                            start = i;
                            maxLength = j - i + 1;
                        }
                    }
                }
            }
        }

        // Extract the longest palindromic substring
        return s.substring(start, start + maxLength);
    }
}

Python Implementation:

def longestPalindrome(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]  # DP table
    start, max_length = 0, 1  # Track the start and max length of the palindrome

    for j in range(n):
        for i in range(j, -1, -1):
            if s[i] == s[j]:  # Check if characters match
                if j - i == 1 or i == j or dp[i + 1][j - 1] == 1:
                    dp[i][j] = 1  # Mark as a palindrome
                    if j - i + 1 > max_length:  # Update the longest palindrome
                        start = i
                        max_length = j - i + 1

    # Extract the longest palindromic substring
    return s[start:start + max_length]

C++ Implementation:

#include 
#include 
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector> dp(n, vector(n, 0)); // DP table
        int start = 0, maxLength = 1; // Track the start and max length of the palindrome

        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                if (s[i] == s[j]) { // Check if characters match
                    if (j - i == 1 || i == j || dp[i + 1][j - 1] == 1) {
                        dp[i][j] = 1; // Mark as a palindrome
                        if (j - i + 1 > maxLength) { // Update the longest palindrome
                            start = i;
                            maxLength = j - i + 1;
                        }
                    }
                }
            }
        }

        // Extract the longest palindromic substring
        return s.substr(start, maxLength);
    }
};