Longest Palindromic Substring Medium ​

Question ​

Given a string s, return the longest palindromic substring in s.

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Input: s = "cbbd"
Output: "bb"

1 <= s.length <= 1000
s consist of only digits and English letters.

Solution ​

def longestPalindrome(s):
    def expandAroundCenter(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    longest = ""

    for i in range(len(s)):
        odd_palindrome = expandAroundCenter(i, i)
        even_palindrome = expandAroundCenter(i, i + 1)

        if len(odd_palindrome) > len(longest):
            longest = odd_palindrome
        if len(even_palindrome) > len(longest):
            longest = even_palindrome

    return longest

public String longestPalindrome(String s) {
    String longest = "";

    for (int i = 0; i < s.length(); i++) {
        String oddPalindrome = expandAroundCenter(s, i, i);
        String evenPalindrome = expandAroundCenter(s, i, i + 1);

        if (oddPalindrome.length() > longest.length()) {
            longest = oddPalindrome;
        }
        if (evenPalindrome.length() > longest.length()) {
            longest = evenPalindrome;
        }
    }

    return longest;
}

private String expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return s.substring(left + 1, right);
}

function longestPalindrome(s) {
  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return s.slice(left + 1, right);
  }

  let longest = "";

  for (let i = 0; i < s.length; i++) {
    let oddPalindrome = expandAroundCenter(i, i);
    let evenPalindrome = expandAroundCenter(i, i + 1);

    if (oddPalindrome.length > longest.length) {
      longest = oddPalindrome;
    }
    if (evenPalindrome.length > longest.length) {
      longest = evenPalindrome;
    }
  }

  return longest;
}

Notes ​

You are given a string s. You need to find the longest palindromic substring within s.

A palindrome is a string that reads the same forwards as it does backwards.

Time and Space Complexity Analysis: ​

The time complexity of the given solutions is O(n^2) due to the nested loops in the expandAroundCenter function. In the worst case, each character will be treated as a center for expansion.

The space complexity for all solutions is O(1) because only a few extra variables are used to store the results.

Keep in mind that there are more advanced algorithms like Manacher's algorithm that can solve this problem with linear time complexity (O(n)), but they involve more complex implementation.