Longest Palindromic Substring: Identifying Maximum Symmetry

The "Longest Palindromic Substring" problem involves finding the longest contiguous substring within a given string that is a palindrome.

Problem Statement

Given a string s, return the longest palindromic substring in s. A palindrome is a sequence of characters that reads the same forward and backward.

Example

• Input: "babad"
• Output: "bab" (Note: "aba" is also a valid answer)

Solution Approach - Expand Around Center

function longestPalindrome(s: string): string {
  if (!s || s.length < 2) return s;

  let start = 0,
    end = 0;
  for (let i = 0; i < s.length; i++) {
    let len1 = expandAroundCenter(s, i, i); // Odd length palindrome
    let len2 = expandAroundCenter(s, i, i + 1); // Even length palindrome
    let len = Math.max(len1, len2);
    if (len > end - start) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }
  return s.substring(start, end + 1);
}

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

Breaking Down the Solution

• Center Expansion Technique: For each character in s, expand around it to find the longest palindrome.
• Handle Even and Odd Length: Check for palindromes of both odd and even lengths.
• Update Maximum Bounds: Update the start and end indices of the longest palindrome found.

Solution in typescript

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

  let start = 0,
    maxLength = 1;

  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(s, i, i); // Odd length palindrome
    expandAroundCenter(s, i, i + 1); // Even length palindrome
  }

  function expandAroundCenter(str: string, left: number, right: number) {
    while (left >= 0 && right < str.length && str[left] === str[right]) {
      if (right - left + 1 > maxLength) {
        start = left;
        maxLength = right - left + 1;
      }
      left--;
      right++;
    }
  }

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

In this TypeScript solution:

• The function longestPalindrome takes a string s as input.
• Two pointers (left and right) are used to expand around each character in the string to check for palindromes.
• The function expandAroundCenter expands around the center (the current character for odd length and between the current and next character for even length) and updates the start and maxLength if a longer palindrome is found.
• The substring method is used to extract and return the longest palindromic substring.

This approach effectively finds the longest palindromic substring by checking each character as the center of potential odd and even length palindromes.

The two-pointers approach for finding the longest palindromic substring is already quite efficient, particularly for its simplicity and directness in handling the problem. However, there are a couple of strategies that can be applied to optimize this solution further:

1. Early Termination: If the remaining substring is shorter than the current longest palindrome found, you can stop the search. This optimization helps reduce the number of unnecessary expansions.
2. Skip Identical Characters: When expanding around the center, if you encounter a group of identical characters, you can skip them in one step instead of expanding one character at a time. This can speed up the search in cases where there are long runs of the same character.

Here's how you could implement these optimizations:

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

  let start = 0,
    maxLength = 1;

  for (let i = 0; i < s.length; i++) {
    if (s.length - i <= maxLength / 2) break; // Early termination
    expandAroundCenter(s, i, i); // Odd length palindrome
    expandAroundCenter(s, i, i + 1); // Even length palindrome
  }

  function expandAroundCenter(str: string, left: number, right: number) {
    while (left >= 0 && right < str.length && str[left] === str[right]) {
      left--;
      right++;
    }
    // Adjust left and right to the last valid palindrome
    left++;
    right--;

    if (right - left + 1 > maxLength) {
      start = left;
      maxLength = right - left + 1;
    }
  }

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

These optimizations can improve performance in specific scenarios, especially for longer strings or strings with many repeated characters. However, the fundamental time complexity of the algorithm remains O(n^2), as it still needs to consider each character as a potential center of a palindrome.

Conclusion

The Longest Palindromic Substring problem is a fascinating challenge in string processing, showcasing techniques like center expansion to find symmetrical patterns in text.