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 a dynamic programming approach or an expanding around center approach. We'll use the expanding around center approach for its simplicity and efficiency.

1. Initialization: Create a variable longestPalindrome to store the longest palindrome found so far, initialized to an empty string.

2. Iteration: Iterate through each character of the string s as a potential center of a palindrome.

3. Expanding: For each character, consider two scenarios:

   • Odd length palindromes: Expand outwards from the current character, checking if the characters at the left and right are equal. Continue expanding until the characters are unequal or you reach the boundaries of the string.
   • Even length palindromes: Consider two adjacent characters as the center. Expand outwards, checking if the characters at the left and right are equal. Continue expanding until the characters are unequal or you reach the boundaries of the string.

4. Update: If a longer palindrome is found in either the odd or even length expansion, update longestPalindrome.

5. Return: After iterating through all characters, return longestPalindrome.

Explanation

The expanding around center approach cleverly handles both odd and even length palindromes by treating each character (and each pair of adjacent characters) as a potential center. Expanding outwards ensures that we find the longest palindrome centered at that point. The comparison and update steps efficiently track the longest palindrome found so far. This avoids unnecessary computations compared to a brute-force approach that checks all possible substrings.

Code

function longestPalindrome(s: string): string {
  let longestPalindrome = "";

  for (let i = 0; i < s.length; i++) {
    // Odd length palindromes
    let left = i;
    let right = i;
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > longestPalindrome.length) {
        longestPalindrome = s.substring(left, right + 1);
      }
      left--;
      right++;
    }

    // Even length palindromes
    left = i;
    right = i + 1;
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > longestPalindrome.length) {
        longestPalindrome = s.substring(left, right + 1);
      }
      left--;
      right++;
    }
  }

  return longestPalindrome;
}

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), the algorithm might have to expand outwards from each character, leading to quadratic time complexity.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input string size. We only store a few variables to track the longest palindrome and the expansion indices.