# 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:

1. 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.
2. Fill the array: For each substring of `s`, set `dp[i][j]` to `true` if the substring is a palindrome.
3. 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

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

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 😄! 