Coding Interview Questions | Longest Palindromic Substring

February 4th, 2024

Longest Palindromic Substring Problem Introduction:

This summary will talk about my solution to the longest palindromic substring problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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

How do you solve the Longest Palindromic Substring Problem?

Solution:

const isPalindrome = (s: string) => {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
};

function longestPalindrome(s: string): string {
  const lastSeenCharIdxMap = new Map<string, number[]>();
  const longestPalindromes: string[] = [];

  for (let sIdx = 0; sIdx < s.length; sIdx++) {
    const char = s[sIdx];
    const lastSeenCharIdxs = lastSeenCharIdxMap.get(char);

    if (lastSeenCharIdxs === undefined) {
      longestPalindromes.push(char);
      lastSeenCharIdxMap.set(char, [sIdx]);
    } else {
      for (const idx of lastSeenCharIdxs) {
        const palindromeCandidate = s.slice(idx, sIdx + 1);

        if (isPalindrome(palindromeCandidate)) {
          longestPalindromes.push(palindromeCandidate);
          break;
        }
      }

      lastSeenCharIdxMap.set(char, [...lastSeenCharIdxs, sIdx]);
    }
  }
  let longestPalindrome = "";

  for (const pal of longestPalindromes) {
    if (pal.length > longestPalindrome.length) {
      longestPalindrome = pal;
    }
  }
  return longestPalindrome;
}

Longest Palindromic Substring Solution Summary:

Below is a breakdown of the key aspects of the solution above for finding the longest palindromic substring:

1. Palindrome Checking Function:

The algorithm defines a utility function isPalindrome that checks if a given string is a palindrome. It iterates from both ends towards the center, comparing characters.

2. Tracking Last Seen Indices:

The algorithm maintains a map (lastSeenCharIdxMap) to keep track of the last seen indices for each character in the input string.

3. Identifying Palindromes:

For each character in the input string, the algorithm retrieves the last seen indices and checks for palindromes by expanding around those indices. If a palindrome is found, it is added to the list of potential longest palindromes.

4. Updating Longest Palindrome:

The algorithm iterates through the list of potential longest palindromes and updates the longestPalindrome variable with the maximum length palindrome.

5. Final Result:

The function returns the longestPalindrome, representing the longest palindromic substring in the given input string.

Complexities:

1. Time Complexity:

   • The algorithm iterates through the characters of the input string, and for each character, it may iterate through the last seen indices to identify palindromes.
   • The time complexity is influenced by the nested iterations, resulting in an average time complexity of O(n^2), where n is the length of the input string.

2. Space Complexity:

   • The algorithm uses additional space to store last seen indices and potential longest palindromes.
   • The space complexity is O(n), where n is the length of the input string.