5 Longest Palindromic Substring
Problem Statement
Given a string s, return the longest palindromic substring in s.
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Approach
BF: Loop through every character in the string, get all substrings and check for being palindrome. O(N * N2)
Optimized: We can use a center based approach where we expand via a helper function from each characters center outward. The expand happens via a while function respecting the bounds from our pointers (incoming indexes) and checking if the two characters are the same. If so we assign the sliced string to longest. At the end of every iteration we decrease the left pointer and increase the right pointer.
Solution
const longestPalindrome = (s) => {
let longest = "";
const expandAroundCenter = (l, r) => {
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l + 1 > longest.length) {
longest = s.slice(l, r + 1);
}
l--;
r++;
}
};
for (let i = 0; i < s.length; i++) {
expandAroundCenter(i, i); // Odd-length palindromes
expandAroundCenter(i, i + 1); // Even-length palindromes
}
return longest;
};