The Longest Palindromic Substring in JavaScript

Strings are fundamental structures in computer science, and within this domain, palindromes hold a special intrigue. A palindrome is a string that reads the same backwards as forwards, like "level" or "deified", or "radar' (hence the image at the top of this article).

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

Given a string, find the longest contiguous substring which is palindromic. For instance, take the string forgeeksskeegfor. Whilst geeksskeeg and eeksskee are both palindromic substrings, the longest one is geeksskeeg at ten characters long. Obviously, it's a little easier when the substrings are actual words like racecar, rather than what reads like 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

As with many algorithmic challenges, there are many different paths we can follow to a solution. The efficiency and practicality of each can vary, making it crucial to understand the nuances of each approach. Here are the four that I'm aware of to solve this 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 iteratively checks every possible substring to see if it's a palindrome and if it's the longest palindrome found so far.

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(): This helper function checks if a string s is a palindrome by reversing the string and comparing it to the original before returning a boolean.
• 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(): This is a helper function which treats the string s as potentially having a palindrome centred around indices left and right. It attempts to expand outward from these indices as long as the characters it encounters on each side match, thereby finding the palindrome.
• longestPalindromeEAC(): This is the main function, it checks every character (and between every pair of characters) in the string as a potential centre of a palindrome. For each centre, it tries to expand using the helper function and keeps track of the longest palindrome found.

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. P array:

   An array P of the same length as the transformed string is initialised to store the palindrome radius for each character in 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 every character under consideration as a potential palindrome centre, its "mirror" position about the current centre C is found. If this mirrored position lies within the bounds of the current palindrome, its palindrome radius is used as a starting point.

5. Expansion:

   Starting from the mirrored palindrome radius or 0 (whichever is smaller), an attempt is made to expand the palindrome centred at the current position.

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

Whilst the Brute Force approach is very simplistic, its inefficiency makes it less suitable for larger strings. Dynamic Programming provides a better method, although it might consume considerable memory in doing so to store the table. The Expand Around Center approach balances both space and time efficiency and would tend to be the solution I would personally prefer. However, for those seeking sheer efficiency and speed, Manacher's Algorithm is by far and away the winner, albeit with significant complexity.

In understanding these algorithms, we gain insights into various strategies for string manipulation, enriching our problem‑solving toolkit in web development and maybe showing off our technical prowess a little in the process.