Hello friends,
If you come here to check the solution of the following question.
Longest Palindromic Substring in javascript
this question is asked in LeetCode as a Longest Palindromic Substring (Question Number -5) and its difficulty is medium.
So let’s first understand the question.
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
So the solution to the above question is.
/**
* @param {string} s
* @return {boolean}
*/
var longestPalindrome = function(s) {
let startIndex = 0;
let maxLength = 1;
function expandMiddle(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
const currentPalindromeLength = right - left + 1;
if (currentPalindromeLength > maxLength) {
maxLength = currentPalindromeLength;
startIndex = left;
}
left -= 1;
right += 1;
}
}
for (let i = 0; i < s.length; i++) {
expandMiddle(i - 1, i + 1);
expandMiddle(i, i + 1)
}
return s.slice(startIndex,startIndex+maxLength)
};
The complexity of the solution is as follows:
Time Complexity: O(n²)- As expanding a palindrome around its center could take up to O(n) & we do this for each character.
Space Complexity: O(1)