The Longest Palindromic Substring in JavaScript

A palindrome reads the same backwards as forwards: "level", "deified", or "radar" (hence the image at the top of this article). Finding the longest one hidden inside a larger string is where the problem becomes more interesting.

The 'Longest Palindromic Substring' problem poses the following challenge:

Given a string, find the longest contiguous substring which is palindromic. For instance, take forgeeksskeegfor: the longest is geeksskeeg, at ten characters. The challenge limits the input to English letters and digits, and the examples below use that same case‑sensitive alphabet. This also keeps the ^, # and $ markers in the Manacher example separate from the input. It's a little easier when the substring reads like a word rather than the name of a Nordic town.

Whilst the problem might sound straightforward, as with many challenges in computer science, the devil is in the detail. The key isn't just to find a solution, it's to find an efficient one ‑ especially when using client‑side technologies like JavaScript. This is where various algorithmic strategies come into play.

Relevance in Web Development

Beyond the more academic interest of algorithms, the longest palindromic substring problem offers insight into string processing techniques. Mastery here can lead to efficient handling of the more complex, real‑world string operations that can be central in web application development.

Four Techniques, Four Solutions

There are several ways to approach this problem, with different costs in time, memory and complexity. For related examples of choosing an algorithm, see validating a palindrome, finding the median of two sorted arrays, adding two numbers as linked lists, solving 4Sum with two pointers, and solving 3Sum after sorting. Here are four approaches to the palindrome problem:

1. Brute Force:

   A straightforward approach, checking all possible combinations.

2. Dynamic Programming:

   Storing previous results to optimise future operations.

3. Expand Around Centre:

   Efficiently exploring possible palindromes based on current positions.

4. Manacher's Algorithm:

   An optimised method designed specifically for this problem.

1. Brute Force

The brute‑force solution checks every possible substring. The TypeScript example includes its isPalindrome() helper, which compares characters from the two ends inwards. The other examples below are also TypeScript.

const isPalindrome = (s: string): boolean => {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
};

const longestPalindromeBruteForce = (s: string): string => {
  let longest: string = '';

  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      const substr: string = s.slice(i, j);
      if (isPalindrome(substr) && substr.length > longest.length) {
        longest = substr;
      }
    }
  }

  return longest;
};

• isPalindrome(): Compare s[left] and s[right], moving inwards until a pair differs or the pointers meet. Return a boolean without needing to reverse the string.
• longestPalindromeBruteForce(): This is the main function which checks every possible substring of s using two nested loops. For each substring, it calls the isPalindrome function to see if it's a palindrome. If it is and it is longer than the previously found palindrome, it updates the longest palindrome found.

2. Dynamic Programming

The dynamic programming technique uses a table to store whether substrings are palindromes or not, which helps derive results for larger substrings from the results of smaller substrings.

const longestPalindromeDP = (s: string): string => {
  const n: number = s.length;
  const dp: boolean[][] = Array(n)
    .fill(null)
    .map(() => Array(n).fill(false));
  let start: number = 0;
  let maxLen: number = 1;

  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
    if (i < n - 1 && s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      start = i;
      maxLen = 2;
    }
  }

  for (let len = 3; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j: number = i + len - 1;
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        start = i;
        maxLen = len;
      }
    }
  }

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

Here, we're using a two‑dimensional boolean array dp where dp[i][j] is true if the substring s[i...j] is a palindrome and false otherwise. It fills this table iteratively, making use of the fact that a string from i to j is a palindrome if the characters at i and j are the same, and the substring from i+1 to j-1 is also a palindrome.

3. Expand Around Centre

For each character in the input string, this method treats it as the centre of a potential palindrome and attempts to expand outwards to find the longest palindrome for which this character serves as the centre.

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

const longestPalindromeEAC = (s: string): string => {
  let longest: string = '';
  for (let i = 0; i < s.length; i++) {
    const palindrome1: string = expandAroundCentre(s, i, i);
    const palindrome2: string = expandAroundCentre(s, i, i + 1);

    if (palindrome1.length > longest.length) {
      longest = palindrome1;
    }
    if (palindrome2.length > longest.length) {
      longest = palindrome2;
    }
  }
  return longest;
};

• expandAroundCentre(): Expand the left and right indices whilst their characters match, then return that palindrome as a substring. This version creates temporary strings; it is not a constant‑auxiliary‑space implementation.
• longestPalindromeEAC(): Try an odd centre at each character and an even centre between adjacent characters, keeping the longest returned substring. The nested expansion takes O(n²) time in the worst case, with O(n) live temporary string storage under the usual copied‑string analysis.

4. Manacher's Algorithm

Manacher's Algorithm is complex and really deserves an article all of its own, but given that it was specifically designed to solve this very problem, it would be amiss not to try and explain this approach too (not that anybody should ever be expected to produce this type of algorithmic solution on their own).

Overview

Manacher's Algorithm is a linear algorithm designed to solve the Longest Palindromic Substring problem in O(n) time complexity, which makes it one of the most efficient algorithms for this problem.

The core idea is to leverage the properties of palindromes to avoid unnecessary computations. By using the information from a palindrome centred at one position, it attempts to infer the lengths of palindromes centred at future positions, thereby saving computations.

An Example Using TypeScript

This starts to waver outside my own coding ability, so please take this code example with a little scepticism, and maybe don't try and use it in a production environment without thorough testing!

const longestPalindromeManacher = (s: string): string => {
  if (!s || s.length === 0) return '';

  // Transform the string to handle even length palindromes
  let T: string = '^';
  for (const char of s) {
    T += `#${char}`;
  }
  T += '#$';

  const n: number = T.length;
  const P: number[] = new Array(n).fill(0);
  let C: number = 0;
  let R: number = 0;

  for (let i = 1; i < n - 1; i++) {
    const mirror = 2 * C - i;

    if (R > i) {
      P[i] = Math.min(R - i, P[mirror]);
    }

    while (T[i + (1 + P[i])] === T[i - (1 + P[i])]) {
      P[i]++;
    }

    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }

  let maxLen: number = 0;
  let centreIndex: number = 0;
  for (let i = 1; i < n - 1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centreIndex = i;
    }
  }

  return s.substr((centreIndex - 1 - maxLen) / 2, maxLen);
};

How It Works

1. Preprocessing:

   The algorithm starts by transforming the input string to a new format that makes handling even‑length palindromes easier. For the string abba, it would become ^#a#b#b#a#$. This allows the algorithm to treat even and odd‑length palindromes uniformly.
2. The P array: Store the palindrome radius at each position of the transformed string.

3. Centre and Right Boundary:

   Two pointers, C (Centre) and R (Right boundary), are maintained. C is the centre of the palindrome currently under consideration, and R is its rightmost boundary.
4. Mirroring: For position i, the corresponding position around centre C is 2 * C - i. When i < R, initialise P[i] to Math.min(R - i, P[mirror]); otherwise it starts at 0.
5. Expansion: Compare the characters immediately outside that initial radius and increase P[i] whilst they match. If this palindrome reaches beyond R, update both C and R.

6. Finding the longest:

   After processing all positions in the transformed string, the maximum value in the P array gives the longest palindrome radius. This can be used to extract the palindrome from the original string.

Concluding Thoughts

Brute force checks a lot of overlapping work. Dynamic programming reduces that repetition with an O(n²) table, whilst centre expansion avoids the table and is usually the approach I find easiest to follow. Manacher's algorithm has linear asymptotic time and space, but that does not make it the fastest choice for every small input. I would want a reason to take on its extra complexity.

The centre‑expansion code shown here returns a string for each centre, so account for those temporary substrings as well as the result. A version that stores only the best start and end indices and slices once at the end can use constant auxiliary space. Actual string allocation and copying costs depend on the JavaScript engine.