Given a string s, your goal is to find and return the longest substring within s that is a palindrome.
A palindrome is a sequence of characters that reads the same backward as forward. For example, "aba" is a palindrome, but "abc" is not.
Input: s = "babad"
Output: "bab"
Input: s = "cbbd"
Output: "bb"
The length of the string s must be between 1 and 1,000 inclusive.
The string s consists only of digits and English letters.
function longestPalindromeDP(s) {
const n = s.length;
if (n === 0) return "";
let start = 0;
let maxLength = 1;
const dp = Array(n).fill(false).map(() => Array(n).fill(false));
for (let i = 0; i < n; i++) {
dp[i][i] = true;
}
for (let length = 2; length <= n; length++) {
for (let i = 0; i <= n - length; i++) {
let j = i + length - 1;
if (s[i] === s[j]) {
if (length === 2) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
if (dp[i][j] && length > maxLength) {
start = i;
maxLength = length;
}
}
}
}
return s.substring(start, start + maxLength);
}
const s1 = "babad";
longestPalindromeDP(s1); //output: bab
const s2 = "cbbd";
longestPalindromeDP(s2); //output: bb
function longestPalindromeManacher(s) {
let t = "#" + s.split("").join("#") + "#";
const n = t.length;
const p = Array(n).fill(0);
let center = 0;
let right = 0;
for (let i = 0; i < n; i++) {
if (i < right) {
p[i] = Math.min(right - i, p[2 * center - i]);
}
while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && t[i + p[i] + 1] === t[i - p[i] - 1]) {
p[i]++;
}
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
}
let maxLen = 0;
let start = 0;
for (let i = 0; i < n; i++) {
if (p[i] > maxLen) {
maxLen = p[i];
start = i;
}
}
return s.substring((start - maxLen) / 2, (start + maxLen) / 2);
}
const s1 = "babad";
longestPalindromeManacher(s1); //output: bab
const s2 = "cbbd";
longestPalindromeManacher(s2); //output: bb
function longestPalindromeExpandAroundCenterMemo(s) {
const memo = new Map();
function isPalindrome(left, right) {
if (left > right) return true;
if (memo.has(`${left},${right}`)) return memo.get(`${left},${right}`);
const result = (left >= 0 && right < s.length && s[left] === s[right] && isPalindrome(left + 1, right - 1));
memo.set(`${left},${right}`, result);
return result;
}
let start = 0;
let maxLength = 0;
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
if (isPalindrome(i, j)) {
if (j - i + 1 > maxLength) {
start = i;
maxLength = j - i + 1;
}
}
}
}
return s.substring(start, start + maxLength);
}
const s1 = "babad";
longestPalindromeExpandAroundCenterMemo(s1); //output: bab
const s2 = "cbbd";
longestPalindromeExpandAroundCenterMemo(s2); //output: bb
function longestPalindromeTwoPointers(s) {
if (s.length === 0) return "";
let maxLen = 1;
let start = 0;
for (let i = 0; i < s.length; i++) {
let l = i;
let r = i;
// Check for odd length palindromes
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
start = l;
}
l--;
r++;
}
l = i;
r = i + 1;
// Check for even length palindromes
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
start = l;
}
l--;
r++;
}
}
return s.substring(start, start + maxLen);
}
const s1 = "babad";
longestPalindromeTwoPointers(s1); //output: bab
const s2 = "cbbd";
longestPalindromeTwoPointers(s2); //output: bb
function longestPalindromeUsingSet(s) {
const palindromes = new Set();
function addPalindromes(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
palindromes.add(s.substring(left, right + 1));
left--;
right++;
}
}
for (let i = 0; i < s.length; i++) {
addPalindromes(i, i);
addPalindromes(i, i + 1);
}
let longest = "";
palindromes.forEach(palindrome => {
if (palindrome.length > longest.length) {
longest = palindrome;
}
});
return longest;
}
const s1 = "babad";
longestPalindromeUsingSet(s1); //output: bab
const s2 = "cbbd";
longestPalindromeUsingSet(s2); //output: bb
function longestPalindromeRecursive(s) {
function isPalindrome(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return s.substring(left + 1, right);
}
let longest = "";
for (let i = 0; i < s.length; i++) {
let pal1 = isPalindrome(i, i);
let pal2 = isPalindrome(i, i + 1);
let currentLongest = pal1.length > pal2.length ? pal1 : pal2;
if (currentLongest.length > longest.length) {
longest = currentLongest;
}
}
return longest;
}
const s1 = "babad";
longestPalindromeRecursive(s1); //output: bab
const s2 = "cbbd";
longestPalindromeRecursive(s2); //output: bb
function longestPalindromeStack(s) {
const stack = [];
let longest = "";
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
const substring = s.substring(i, j + 1);
if (isPalindromeStack(substring)) {
if (substring.length > longest.length) {
longest = substring;
}
}
}
}
return longest;
function isPalindromeStack(str) {
const stack = [];
for (let char of str) {
stack.push(char);
}
let reversed = "";
while (stack.length) {
reversed += stack.pop();
}
return str === reversed;
}
}
const s1 = "babad";
longestPalindromeStack(s1); //output: bab
const s2 = "cbbd";
longestPalindromeStack(s2); //output: bb
function longestPalindromeHashMap(s) {
const map = new Map();
let longest = "";
function isPalindrome(str) {
if (map.has(str)) return map.get(str);
const result = str === str.split("").reverse().join("");
map.set(str, result);
return result;
}
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
const substring = s.substring(i, j + 1);
if (isPalindrome(substring)) {
if (substring.length > longest.length) {
longest = substring;
}
}
}
}
return longest;
}
const s1 = "babad";
longestPalindromeHashMap(s1); //output: bab
const s2 = "cbbd";
longestPalindromeHashMap(s2); //output: bb
The Longest Palindromic Substring problem requires you to identify and return the longest contiguous substring from a given string s that is a palindrome. A palindrome is a sequence that reads the same forwards and backwards.
The Dynamic Programming solution constructs a 2D table to track which substrings are palindromes. By building up solutions for progressively larger substrings based on smaller ones, it efficiently finds the longest palindromic substring.
Manacher's Algorithm preprocesses the string by inserting special characters to handle even-length palindromes uniformly. It maintains an array that records the maximum radius of palindromes centered at each position, achieving linear time complexity.
The Recursive Approach finds palindromes by expanding outward from each character or between characters and compares the length of the resulting palindromes. This approach is straightforward but can be less efficient due to its recursive nature.