This problem was asked by Uber.
You are given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example
function longestPalindrome(s) {
}
console.log(longestPalindrome('babad')); // bab
console.log(longestPalindrome('cbbd')); // bb
Solution
function longestPalindrome(s) {
let longest = "";
for (let i = 0; i < s.length; i++) {
const oddStr = expandFromMiddle(s, i, i);
if (oddStr.length > longest.length) {
longest = oddStr;
}
const evenStr = expandFromMiddle(s, i, i + 1);
if (evenStr.length > longest.length) {
longest = evenStr;
}
}
function expandFromMiddle(str, left, right) {
while (left >= 0 && right < str.length && s[left] === s[right]) {
left--;
right++;
}
return str.slice(left + 1, right);
}
return longest;
}
Explanation
- Iterate through each character in the string
- For each character, expand outwards to find odd and even length palindromes centered at that character
- Use a helper function to expand from the middle, incrementing left and right pointers until reaching different characters
- Keep track of the longest palindrome seen so far
- After checking all characters, return the longest palindrome
Top comments (0)