You will find javascript program and solution at single place.

Monday, 11 July 2022

Longest Palindromic Substring in javascript

 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 <= 1000
  • s consist 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()- As expanding a palindrome around its center could take up to O(n) & we do this for each character.

Space Complexity: O(1)

No comments:

Post a Comment