SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a string s, find the longest palindromic substring in s. A palindrome is a string that reads the same forward and backward. The task is to return the longest substring of s that is a palindrome.

Intuition

To solve this problem efficiently, we need to check each substring to determine if it is a palindrome. Using dynamic programming (DP) can help us avoid redundant computations by storing results of subproblems. We can use a 2D DP table where dp[i][j] indicates whether the substring s[i:j+1] is a palindrome. By building up solutions from smaller substrings to larger ones, we can efficiently find the longest palindromic substring.

Approach

1. Initialize the DP Table:

   • Create a 2D DP array dp where dp[i][j] will be 1 if the substring s[i:j+1] is a palindrome and 0 otherwise.
   • All single-character substrings are palindromes, so set dp[i][i] = 1.
   • For two-character substrings, set dp[i][i+1] = 1 if both characters are the same.

2. Fill the DP Table for Longer Substrings:

   • For substrings longer than 2 characters, use the relation:
     • dp[i][j] = 1 if s[i] == s[j] and dp[i+1][j-1] == 1.

3. Find the Longest Palindromic Substring:

   • Iterate through the DP table to find the longest substring that is marked as a palindrome in dp.

4. Return the Result:

   • Extract and return the longest palindromic substring using the start and maxLen values.

Complexity

Time Complexity:

O(n^2), where n is the length of the string s. This is due to the nested loops that fill the DP table and the substring checks.

Space Complexity:

O(n^2), for storing the DP table. Each cell in the table is used to store whether a substring is a palindrome.

Code

C++

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        
        auto f = [&](auto& f, int i, int j) -> int {
            if (dp[i][j] != -1) return dp[i][j];
            if (i >= j) {
                return dp[i][j] = 1;
            }
            if (s[i] == s[j]) {
                return dp[i][j] = f(f, i + 1, j - 1);
            }
            return dp[i][j] = 0;
        };

        int maxLen = 0;
        int sp = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                if (f(f, i, j)) {
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        sp = i;
                    }
                }
            }
        }
        return s.substr(sp, maxLen);
    }
};

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[-1] * n for _ in range(n)]

        def is_palindrome(i: int, j: int) -> bool:
            if dp[i][j] != -1:
                return dp[i][j] == 1
            if i >= j:
                dp[i][j] = 1
                return True
            if s[i] == s[j]:
                dp[i][j] = is_palindrome(i + 1, j - 1)
                return dp[i][j] == 1
            dp[i][j] = 0
            return False

        max_len = 0
        start = 0

        for i in range(n):
            for j in range(i, n):
                if is_palindrome(i, j):
                    if j - i + 1 > max_len:
                        max_len = j - i + 1
                        start = i

        return s[start:start + max_len]

Java

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        int maxLen = 0;
        int start = 0;
        // Initialize dp array for single characters and two-character substrings
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1; // Single character substrings are palindromes
        }
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = 1; // Two-character substrings are palindromes if both characters are the same
            }
        }
        // Fill dp table for substrings longer than 2 characters
        for (int length = 3; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1] == 1) {
                    dp[i][j] = 1;
                }
            }
        }
        // Find the longest palindromic substring
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (dp[i][j] == 1 && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}

JavaScript

let dp;
function f(s, i, j) {
    if(dp[i][j] != -1) return dp[i][j];
    if(i>=j) {
        return dp[i][j] = 1;
    } 
    if(s[i] == s[j]) { 
        return dp[i][j] = f(s, i+1, j-1);
    }
    return dp[i][j] = 0;
}
var longestPalindrome = function(s) {
    dp = Array(1001);
    for(let i = 0; i < dp.length; i++) {
        dp[i] = Array(1001).fill(-1);
    }
    let n = s.length;
    let maxLen = 0;
    let sp = 0;
    for(let i = 0; i < n; i++) {
        for(let j = i; j < n; j++) {
            if(f(s,i, j)) {
                if(j-i+1 > maxLen) {
                    maxLen = j-i+1;
                     sp = i;
                }
            }
        }
    }
    return s.substr(sp, maxLen);
};