Longest Palindromic Substring medium

Problem Statement

Given a string s, find 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"

Steps

The problem can be solved using dynamic programming or a more efficient approach using expanding around the center. We'll focus on the expanding around the center approach due to its improved time complexity.

1. Initialization: We'll iterate through each character in the string. Each character is a palindrome of length 1. We'll also consider the spaces between characters as potential centers for even-length palindromes.

2. Expanding: For each potential center (a single character or a space between characters), we expand outwards, checking if the characters at the left and right positions are equal. If they are, we continue expanding. We keep track of the longest palindrome found so far.

3. Tracking the Longest Palindrome: We maintain variables to store the start and end indices of the longest palindrome encountered.

Explanation

The expanding around the center approach is efficient because it avoids redundant calculations. Instead of checking all possible substrings, it focuses only on potential palindrome centers and expands outwards. This significantly reduces the number of comparisons needed.

Code

def longestPalindrome(s):
    """
    Finds the longest palindromic substring in a given string.

    Args:
        s: The input string.

    Returns:
        The longest palindromic substring.
    """

    n = len(s)
    if n < 2:
        return s  # Empty or single-character string is a palindrome

    start = 0
    max_len = 1

    for i in range(n):
        # Odd length palindromes
        l, r = i, i
        while l >= 0 and r < n and s[l] == s[r]:
            if r - l + 1 > max_len:
                max_len = r - l + 1
                start = l
            l -= 1
            r += 1

        # Even length palindromes
        l, r = i, i + 1
        while l >= 0 and r < n and s[l] == s[r]:
            if r - l + 1 > max_len:
                max_len = r - l + 1
                start = l
            l -= 1
            r += 1

    return s[start:start + max_len]

Complexity

• Time Complexity: O(n^2), where n is the length of the string. In the worst case (e.g., a string of all the same character), we might need to expand outwards for each character, resulting in a quadratic time complexity. However, this is significantly better than the O(n^3) complexity of a naive approach.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space to store variables. It doesn't use any additional data structures that scale with the input size.