Solving Longest Palindromic Substring in JavaScript: Step-by-Step Guide

Solving the Longest Palindromic Substring in JavaScript: A Step-by-Step Guide

The Longest Palindromic Substring problem is one of the most classic algorithmic challenges you will encounter in coding interviews and competitive programming. It asks a deceptively simple question: given a string, what is the longest contiguous substring that reads the same forwards and backwards? In this tutorial, we will break down the problem, explore multiple solution strategies, and implement an efficient solution in JavaScript.

What Is a Palindrome?

A palindrome is a sequence of characters that remains identical when reversed. For example, "racecar", "madam", and "abba" are all palindromes. A palindromic substring is a contiguous slice of a larger string that itself is a palindrome. Given an input like "babad", the longest palindromic substrings are "bab" and "aba", both of length 3.

Why This Problem Matters

This problem is a staple on platforms like LeetCode (Problem #5) and frequently appears in technical interviews at major tech companies. It matters for several reasons:

• Tests algorithmic thinking: It forces you to weigh trade-offs between brute force and optimized approaches.
• Introduces dynamic programming: It is a gateway problem for understanding DP table construction.
• Teaches the expand-around-center technique: A reusable pattern for many string problems.
• Real-world relevance: Palindrome detection is used in bioinformatics (DNA sequence analysis), text processing, and data validation.

Understanding the Problem Statement

Given a string s of length n, return the longest palindromic substring in s. If multiple answers exist with the same maximum length, returning any one of them is acceptable.

For example:

Input:  "cbbd"
Output: "bb"

Input:  "a"
Output: "a"

Input:  "ac"
Output: "a"  (or "c", both are valid)

Constraints typically include 1 <= s.length <= 1000, and the string consists of printable ASCII characters. The challenge is to find an efficient solution rather than checking every possible substring naively.

Approach 1: Brute Force

The most intuitive approach is to generate every possible substring and check whether each one is a palindrome. While easy to understand, this approach is inefficient.

Implementation

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

function longestPalindromeBruteForce(s) {
  let longest = "";
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (isPalindrome(s, i, j)) {
        const substring = s.slice(i, j + 1);
        if (substring.length > longest.length) {
          longest = substring;
        }
      }
    }
  }
  return longest;
}

console.log(longestPalindromeBruteForce("babad")); // "bab" or "aba"

Complexity Analysis

There are O(n^2) substrings, and checking each one takes O(n) time, giving a total time complexity of O(n^3). The space complexity is O(1) (excluding the output). For strings longer than a few hundred characters, this becomes impractical.

Approach 2: Expand Around Center

A palindrome mirrors around its center. For a string of length n, there are 2n - 1 possible centers — one for each character (odd-length palindromes) and one between each pair of adjacent characters (even-length palindromes). By expanding outward from each center, we can find the longest palindrome in O(n^2) time and O(1) space.

Step-by-Step Logic

• Iterate through each index of the string, treating it as a potential center.
• For each center, expand outward while the characters on both sides match.
• Handle both odd-length centers (single character) and even-length centers (between two characters).
• Track the longest palindrome found across all expansions.

Implementation

function expandAroundCenter(s, left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--;
    right++;
  }
  // Return the length of the palindrome
  return right - left - 1;
}

function longestPalindrome(s) {
  if (!s || s.length < 1) return "";

  let start = 0;
  let end = 0;

  for (let i = 0; i < s.length; i++) {
    const oddLength = expandAroundCenter(s, i, i);     // odd-length palindrome
    const evenLength = expandAroundCenter(s, i, i + 1); // even-length palindrome
    const maxLength = Math.max(oddLength, evenLength);

    if (maxLength > end - start + 1) {
      start = i - Math.floor((maxLength - 1) / 2);
      end = i + Math.floor(maxLength / 2);
    }
  }

  return s.slice(start, end + 1);
}

console.log(longestPalindrome("babad")); // "bab" or "aba"
console.log(longestPalindrome("cbbd"));  // "bb"
console.log(longestPalindrome("a"));     // "a"
console.log(longestPalindrome("racecar")); // "racecar"

How the Index Math Works

After expansion, the palindrome spans from index start to end inclusive. Given the center index i and the palindrome length maxLength:

• start = i - Math.floor((maxLength - 1) / 2)
• end = i + Math.floor(maxLength / 2)

This formula works for both odd and even length palindromes because the floor division naturally handles the asymmetry of even-length centers.

Complexity Analysis

Time complexity is O(n^2) since expanding around a center can take up to O(n) time, and we do this for 2n - 1 centers. Space complexity is O(1), making this approach both efficient and memory-friendly. For most interview scenarios, this is the recommended solution.

Approach 3: Dynamic Programming

Dynamic programming (DP) offers another O(n^2) solution but uses O(n^2) space. The idea is to build a table dp[i][j] that is true if the substring s[i..j] is a palindrome. A substring s[i..j] is a palindrome if s[i] === s[j] and the inner substring s[i+1..j-1] is also a palindrome (or the length is at most 2).

Implementation

function longestPalindromeDP(s) {
  const n = s.length;
  if (n < 1) return "";

  // dp[i][j] = true if s[i..j] is a palindrome
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));

  let start = 0;
  let maxLength = 1;

  // Every single character is a palindrome
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  // Check two-character substrings
  for (let i = 0; i < n - 1; i++) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      start = i;
      maxLength = 2;
    }
  }

  // Check substrings of length 3 and greater
  for (let len = 3; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        start = i;
        maxLength = len;
      }
    }
  }

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

console.log(longestPalindromeDP("babad")); // "bab" or "aba"
console.log(longestPalindromeDP("cbbd"));  // "bb"

Complexity Analysis

Time complexity is O(n^2) because we fill an n x n table. Space complexity is also O(n^2) due to the DP table. While this approach is more memory-intensive than expand-around-center, it is valuable for understanding DP fundamentals and can be extended to related problems like counting palindromic substrings.

Approach 4: Manacher's Algorithm

For those seeking the theoretically optimal solution, Manacher's Algorithm solves the problem in O(n) time. It works by transforming the string to handle even-length palindromes uniformly, then uses previously computed palindrome radii to skip redundant comparisons. While powerful, it is complex to implement and rarely expected in interviews unless explicitly requested.

function longestPalindromeManacher(s) {
  if (!s || s.length < 1) return "";

  // Transform s into T, e.g. "abc" -> "^#a#b#c#$"
  const T = "^#" + s.split("").join("#") + "#$";
  const n = T.length;
  const P = new Array(n).fill(0);
  let C = 0, R = 0;

  for (let i = 1; i < n - 1; i++) {
    const mirror = 2 * C - i;
    if (i < R) {
      P[i] = Math.min(R - i, P[mirror]);
    }

    // Expand around center i
    while (T[i + P[i] + 1] === T[i - P[i] - 1]) {
      P[i]++;
    }

    // Update center and right boundary
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }

  // Find the maximum element in P
  let maxLen = 0;
  let centerIndex = 0;
  for (let i = 1; i < n - 1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }

  const start = Math.floor((centerIndex - maxLen) / 2);
  return s.slice(start, start + maxLen);
}

console.log(longestPalindromeManacher("babad")); // "bab" or "aba"
console.log(longestPalindromeManacher("cbbd"));  // "bb"

Manacher's Algorithm is an impressive optimization but should be reserved for cases where O(n) performance is genuinely required, such as processing very large strings in production systems.

Comparing the Approaches

• Brute Force: O(n^3) time, O(1) space — too slow for real use.
• Expand Around Center: O(n^2) time, O(1) space — best balance for interviews.
• Dynamic Programming: O(n^2) time, O(n^2) space — great for learning DP.
• Manacher's Algorithm: O(n) time, O(n) space — optimal but complex.

Best Practices

• Always handle edge cases: Empty strings, single characters, and strings with no palindromes longer than 1 should be handled explicitly.
• Prefer expand-around-center for interviews: It is concise, efficient, and easy to explain on a whiteboard.
• Avoid unnecessary string slicing: Track start and end indices instead of repeatedly creating substrings, which costs extra memory.
• Test with diverse inputs: Include even-length palindromes, odd-length palindromes, all-same-character strings, and strings with no repeating characters.
• Comment your index math: The center-to-boundary calculations are easy to get wrong; clear comments help maintainability.
• Consider case sensitivity: Decide whether "Aa" should be treated as a palindrome based on your requirements.

Testing Your Solution

Robust testing ensures your implementation handles edge cases correctly. Here is a test suite covering common scenarios:

function runTests() {
  const testCases = [
    { input: "babad", expectedLength: 3 },
    { input: "cbbd", expectedLength: 2 },
    { input: "a", expectedLength: 1 },
    { input: "ac", expectedLength: 1 },
    { input: "racecar", expectedLength: 7 },
    { input: "abba", expectedLength: 4 },
    { input: "aaaa", expectedLength: 4 },
    { input: "abcde", expectedLength: 1 },
    { input: "", expectedLength: 0 },
  ];

  testCases.forEach(({ input, expectedLength }) => {
    const result = longestPalindrome(input);
    const passed = result.length === expectedLength;
    console.log(
      `Input: "${input}" | Result: "${result}" | ` +
      `Expected length: ${expectedLength} | ${passed ? "PASS" : "FAIL"}`
    );
  });
}

runTests();

Common Pitfalls

• Off-by-one errors in slicing: JavaScript's slice(start, end) excludes end, so remember to use slice(start, end + 1) when end is inclusive.
• Forgetting even-length palindromes: Many beginners only check single-character centers and miss palindromes like "bb".
• Incorrect center calculation: The formula for converting palindrome length back to start and end indices is a frequent source of bugs.
• Not handling empty input: Always guard against null, undefined, or empty strings at the top of your function.

Conclusion

The Longest Palindromic Substring problem is a fantastic exercise in algorithmic problem-solving that rewards careful analysis of trade-offs. While the brute force approach is a natural starting point, the expand-around-center technique offers the best combination of efficiency, clarity, and interview readiness. Dynamic programming provides a valuable learning opportunity for table-based reasoning, and Manacher's Algorithm demonstrates how advanced techniques can push performance to linear time. By mastering these approaches, understanding their complexities, and following best practices around edge cases and testing, you will be well-equipped to tackle this problem confidently in any technical interview or real-world application.