LeetCode #5 - Longest Palindromic Substring

Hello, coding enthusiasts! 👋 Today, we’re going to unravel another challenging problem from LeetCode: “Longest Palindromic Substring”.

Problem Statement

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

Constraints

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

Examples

Example 1:

Plaintext

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

Example 2:

Plaintext

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

Analysis

A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward, ignoring spaces, punctuation, and capitalization.

Our task is to find the longest palindromic substring in a given string.

Approach

The most efficient approach to solve this problem is to use dynamic programming. Here’s how it works:

Initialize a 2D array: Create a 2D boolean array dp where dp[i][j] is true if the substring s[i...j] is a palindrome.
Fill the array: For each substring of s, set dp[i][j] to true if the substring is a palindrome.
Find the longest palindrome: Iterate over dp to find the longest substring where dp[i][j] is true.

Time Complexity

The time complexity for this approach is O(n^2), where n is the length of the string. This is because we’re filling a 2D array of size n^2.

Space Complexity

The space complexity is also O(n^2), as we’re using a 2D array of size n^2 to store whether each substring is a palindrome.

Code

Here’s the Python and JavaScript code for this approach:

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2 or s == s[::-1]:
            return s
        start, max_len = 0, 1
        for i in range(1, len(s)):
            odd = s[i-max_len-1:i+1]  # len(odd) = max_len + 2
            even = s[i-max_len:i+1]  # len(even) = max_len + 1
            if i - max_len - 1 >= 0 and odd == odd[::-1]:
                start = i - max_len - 1
                max_len += 2
                continue
            if even == even[::-1]:
                start = i - max_len
                max_len += 1
        return s[start:start + max_len]

JavaScript

var longestPalindrome = function(s) {
    if (s.length < 2) {
        return s;
    }
    let start = 0, end = 0;
    for (let i = 0; i < s.length; i++) {
        let len1 = expandAroundCenter(s, i, i);
        let len2 = expandAroundCenter(s, i, i + 1);
        let len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - Math.floor((len - 1) / 2);
            end = i + Math.floor(len / 2);
        }
    }
    return s.substring(start, end + 1);
};

var expandAroundCenter = function(s, left, right) {
    while (left >= 0 && right < s.length && s

[left] === s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
};

Conclusion

In this post, we tackled the “Longest Palindromic Substring” problem from LeetCode using dynamic programming. This solution has a time complexity of O(n^2) and a space complexity of O(n^2).

Happy coding 😄!

Learn More:

LeetCode #5 – Longest Palindromic Substring