5. Longest Palindromic Substring

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad" Output: "bab" Note: "aba" is also a valid answer. 

Example 2:

Input: "cbbd" Output: "bb" 

Solution

/** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { var start = 0; var end = 0; var len = s.length; var num = 0; for (var i = 0; i < len; i++) { num = Math.max(expandAroundCenter(s, i, i), expandAroundCenter(s, i, i + 1)); if (num > end - start) { start = i - Math.floor((num - 1) / 2); end = i + Math.floor(num / 2); } } return s.slice(start, end + 1); }; var expandAroundCenter = function (s, left, right) { var l = left; var r = right; var len = s.length; while (l >= 0 && r < len && s[l] === s[r]) { l--; r++; } return r - l - 1; }; 

Explain:

遍历每个字符，检查以这个字符或相邻两个字符为中心是否回文，记录最长的回文字符位置。

Complexity:

• Time complexity : O(n^2).
• Space complexity : O(1).

/** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { let startIndex = 0; let maxLength = 1; function expandAroundCenter(left, right) { while (left >=0 && right < s.length && s[left] === s[right]) { const currentPalLength = right - left + 1; if (currentPalLength > maxLength) { maxLength = currentPalLength; startIndex = left; } left -= 1; right += 1; } } for (let i = 0; i < s.length; i++) { expandAroundCenter(i-1, i+1); expandAroundCenter(i, i+1); } return s.slice(startIndex, startIndex + maxLength) }; 

Complexity:

• Time complexity : O(n^2).
• Space complexity : O(1).