Weekly Coding Problem Solving

Given a string, find the longest palindromic contiguous substring. If there are more than one with the maximum length, return any one.

For example, the longest palindromic substring of “aabcdcb” is “bcdcb”. The longest palindromic substring of “bananas” is “anana”.

To find the longest palindromic contiguous substring in a given string, we can use the expand around center technique. This approach efficiently finds palindromic substrings by expanding around each character (or pair of characters) and checking for the longest palindrome.

Approach

1. A palindrome reads the same forwards and backwards. To find the longest palindrome, we can check each character and its surrounding characters.
2. For each character in the string, consider it as the center of a palindrome and expand outward to see how far the palindrome extends.
3. There are two cases to consider for each character:

• A palindrome with an odd length (centered around one character).
• A palindrome with an even length (centered around a pair of characters).

Get Hemant Kumar Maurya’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

4. Keep track of the longest palindrome found during this expansion.

Implementation

function longestPalindrome(s) {
    if (s.length < 2) return s;

    let start = 0, maxLength = 1;

    // Helper function to expand around center
    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        // Calculate the length of the palindrome
        return right - left - 1;
    }

    for (let i = 0; i < s.length; i++) {
        // Odd length palindromes (centered at i)
        const len1 = expandAroundCenter(i, i);
        // Even length palindromes (centered between i and i + 1)
        const len2 = expandAroundCenter(i, i + 1);

        // Determine the maximum length palindrome for this center
        const len = Math.max(len1, len2);
        if (len > maxLength) {
            maxLength = len;
            // Update start position of the longest palindrome found
            start = i - Math.floor((len - 1) / 2);
        }
    }

    return s.substring(start, start + maxLength);
}

// Example usage
console.log(longestPalindrome("aabcdcb")); // Output: "bcdcb"
console.log(longestPalindrome("bananas")); // Output: "anana"

Explanation

• expandAroundCenter(left, right): Expands outward from the center, checking if characters on both sides are the same. Returns the length of the palindrome found.
• Loop through each character in the string and check for both odd-length and even-length palindromes centered at each character.
• Update start and maxLength if a longer palindrome is found.
• Finally, return the longest palindromic substring using s.substring(start, start + maxLength).

Complexity

• Time Complexity: O(n^2) where n is the length of the string. For each character, we expand outward to find the palindrome.
• Space Complexity: O(1) since we only use a few extra variables.