Longest Palindromic Substring

Updated on 02 June, 2025
Longest Palindromic Substring header image

Problem Statement

The task is to find the longest substring within a given string s that reads the same forwards and backwards—a characteristic known as being palindromic. Given the constraint of the string's length, which might reach up to 1000 characters, and the fact that it comprises only English letters and digits, the solution must efficiently handle diverse cases while respecting the boundaries set by these limitations. The variety in characters also hints at multiple palindromic substrings, but only the longest one is desired for the output.

Examples

Example 1

Input:

s = "babad"

Output:

"bab"

Explanation:

"aba" is also a valid answer.

Example 2

Input:

s = "cbbd"

Output:

"bb"

Constraints

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Approach and Intuition

The challenge involves identifying the longest palindromic substring from a given string. Here’s an intuitive breakdown of how one might approach the problem:

  1. Brute Force (Not Optimal): One might consider checking every possible substring and verify if it's palindromic. Although this method guarantees finding the longest palindrome, it becomes computationally expensive as s.length approaches 1000, making it an impractical option for longer strings.

  2. Expand Around Center: A more efficient approach involves selecting every possible center for potential palindromes and expanding outwards as long as characters on both sides match. This method takes advantage of:

    • Odd length palindromes (like "racecar") where the center is a single character.
    • Even length palindromes (like "deed") where the center is in between two characters.

    For each character (or pair of adjacent characters, in the case of even-length palindromes), attempt to expand as far as possible while the substring remains a palindrome. Log the maximum length encountered.

  3. Dynamic Programming: This involves using a table to store whether substrings are palindromes and using this information to build solutions for larger substrings. However, this may involve complex indexing and isn't as space efficient.

  4. Manacher's Algorithm: It is the most complex but the most efficient algorithm for this problem, providing a linear time solution. However, due to its complexity, it's generally not the first approach unless performance is a critical concern.

Given tasks and constraints—like the maximum possible length of 1000 characters—the Expand Around Center strategy offers a balanced approach between complexity and efficiency. It allows us to leverage the nature of palindromes for a relatively straightforward and efficient solution.

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp
class Solution {
public:
    string findLongestPalindrome(string str) {
        string modifiedString = "#";
        for (char ch : str) {
            modifiedString += ch;
            modifiedString += "#";
        }

        int strLength = modifiedString.length();
        vector<int> radii(strLength, 0);
        int C = 0;
        int R = 0;

        for (int i = 0; i < strLength; i++) {
            int mirror = 2 * C - i;

            if (i < R) {
                radii[i] = min(R - i, radii[mirror]);
            }

            while (i + 1 + radii[i] < strLength &&
                   i - 1 - radii[i] >= 0 &&
                   modifiedString[i + 1 + radii[i]] ==
                       modifiedString[i - 1 - radii[i]]) {
                radii[i]++;
            }

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

        int longestLength = 0;
        int bestCenter = 0;
        for (int i = 0; i < strLength; i++) {
            if (radii[i] > longestLength) {
                longestLength = radii[i];
                bestCenter = i;
            }
        }

        int startIndex = (bestCenter - longestLength) / 2;
        string longest_substring = str.substr(startIndex, longestLength);

        return longest_substring;
    }
};

The given C++ code implements a solution to find the longest palindromic substring within a given string. The approach used in this solution involves expanding from the center and modifying the string by placing a "#" between each character as well as at the beginning and end. This technique converts the string so that palindrome checks for even length can be done in the same way as for odd length.

Here’s a concise breakdown of the algorithm used:

  • Insert a "#" character between each character of the input string and also at the beginning and end. This transformation handles the unified approach for finding palindromes of both odd and even lengths.
  • Initialize an array radii where radii[i] represents the radius of the palindrome centered at i in the modified string including the center character itself.
  • Use two pointers, C (center of the current rightmost palindrome) and R (right boundary of this palindrome), to track the farthest reached palindrome.
  • Iterate through each character of the modified string:
    • Calculate the mirror index of the current character based on the center C.
    • Use previously known palindromic radii values from the radii array to avoid unnecessary recalculations.
    • Attempt to expand the palindrome centered at each character until the conditions (staying within bounds and characters matching on both sides) are met.
    • If expanding this palindrome goes beyond the current known right boundary (R), update C and R.
  • After the main loop, determine the longest palindrome by finding the max value in the radii array.
  • Translate the index and length from the modified string back to indexes suitable for the original unmodified string.

Ultimately, the function extracts the substring of the original string which represents the longest palindrome and returns it. This implementation efficiently finds the longest palindromic substring in linear time relative to the size of the input string.

java
class Solution {
    public String findLongestPalindrome(String input) {
        StringBuilder modifiedString = new StringBuilder("#");
        for (char c : input.toCharArray()) {
            modifiedString.append(c).append("#");
        }

        int length = modifiedString.length();
        int[] radii = new int[length];
        int currentCenter = 0;
        int currentRadius = 0;

        for (int i = 0; i < length; i++) {
            int reflectedIndex = 2 * currentCenter - i;

            if (i < currentRadius) {
                radii[i] = Math.min(
                    currentRadius - i,
                    radii[reflectedIndex]
                );
            }

            while (
                i + 1 + radii[i] < length &&
                i - 1 - radii[i] >= 0 &&
                modifiedString.charAt(i + 1 + radii[i]) ==
                    modifiedString.charAt(i - 1 - radii[i])
            ) {
                radii[i]++;
            }

            if (i + radii[i] > currentRadius) {
                currentCenter = i;
                currentRadius = i + radii[i];
            }
        }

        int maxLen = 0;
        int centerIdx = 0;
        for (int i = 0; i < length; i++) {
            if (radii[i] > maxLen) {
                maxLen = radii[i];
                centerIdx = i;
            }
        }

        int startIdx = (centerIdx - maxLen) / 2;
        String result = input.substring(
            startIdx,
            startIdx + maxLen
        );

        return result;
    }
}

In the provided Java solution for finding the longest palindromic substring, the code uses the Manacher's algorithm, which is efficient for this problem with a linear time complexity. Below is a breakdown of how the solution works:

  • Start by transforming the original input string to include '#' characters between each character. This modification helps handle palindromes of even length uniformly with those of odd length.

  • Initiate an array radii to store the radius of the longest palindrome at each character in the modified string.

  • As iteration through the modifiedString progresses, check if the current character can mirror the palindrome properties of the character at a reflected position from a known center currentCenter. Adjust the radius for this character based on comparisons.

  • For each character, extend the radius of the palindrome as far as symmetry holds on both sides.

  • Update the currentCenter and currentRadius if the palindrome extends beyond the previously known bounds.

  • After the main loop, determine the longest palindrome by scanning through the radii array and calculate the starting index of this palindrome in the original input string by adjusting for the added '#' characters.

  • Finally, extract the longest palindromic substring using this start index and the length from the radii array.

This concise algorithm effectively finds the longest palindromic substring in a given string by cleverly utilizing character mirroring and dynamic center shifting, ensuring the processing time remains linear with respect to the input size. This is significantly more efficient than simpler quadratic or cubic solutions.

c
#include "stdlib.h"
#include "string.h"

char* findLongestPalindromeSubstr(char* input_string) {
    int length = strlen(input_string);
    char* modified_string = (char*)malloc(sizeof(char) * (2 * length + 2));
    modified_string[0] = '#';
    int position = 1;
    for (int idx = 0; idx < length; idx++) {
        modified_string[position++] = input_string[idx];
        modified_string[position++] = '#';
    }
    modified_string[position] = '\0';

    int n = strlen(modified_string);
    int* radii = (int*)malloc(n * sizeof(int));
    memset(radii, 0, n * sizeof(int));
    int center_pos = 0;
    int current_radius = 0;

    for (int i = 0; i < n; i++) {
        int mirror = 2 * center_pos - i;

        if (i < current_radius) {
            radii[i] = (current_radius - i > radii[mirror]
                                       ? radii[mirror]
                                       : current_radius - i);
        }

        while (i + 1 + radii[i] < n &&
               i - 1 - radii[i] >= 0 &&
               modified_string[i + 1 + radii[i]] ==
                   modified_string[i - 1 - radii[i]]) {
            radii[i]++;
        }

        if (i + radii[i] > current_radius) {
            center_pos = i;
            current_radius = i + radii[i];
        }
    }

    int max_length = 0;
    int optimal_center = 0;
    for (int i = 0; i < n; i++) {
        if (radii[i] > max_length) {
            max_length = radii[i];
            optimal_center = i;
        }
    }

    int initial_index = (optimal_center - max_length) / 2;
    char* result_palindrome = (char*)malloc(max_length + 1);
    strncpy(result_palindrome, &input_string[initial_index], max_length);
    result_palindrome[max_length] = '\0';

    free(modified_string);
    free(radii);

    return result_palindrome;
}

The provided C code implements a function to find the longest palindromic substring in a given string. The approach used is an optimized version that utilizes the Manacher's Algorithm that effectively reduces the complexity of finding the longest palindrome. Here's a brief breakdown of key operations:

  • First, transform the input string by inserting a # character between each character and at the ends. This helps in handling even-length palindromes uniformly with odd-length ones.
  • Initialize arrays to keep track of the current longest radii of palindromes for each character in the transformed string.
  • Use a center expansion technique where for each character in the modified string, expand around that character to find palindromes, while keeping track of the longest palindrome found.
  • Update the center and the right boundary of the palindrome whenever the expanded palindrome surpasses the current known boundaries.
  • Scan through the array of radii to determine the maximum length of the palindrome and its central position.
  • Extract the longest palindromic substring from the original input string using indices computed from the modified string's center and radius information.
  • Memory management is handled explicitly using malloc and free to allocate and deallocate memory used by helper data structures.

The implementation ensures efficient memory usage and processing, handling cases to compute the longest palindromic substring in linear time, which is well-suited for large input strings.

js
var findLongestPalindrome = function (stringInput) {
    let transformedString = "#";
    for (let character of stringInput) {
        transformedString += character;
        transformedString += "#";
    }

    let lengthOfTransformed = transformedString.length;
    let radiusArray = new Array(lengthOfTransformed).fill(0);
    let currentCenter = 0;
    let currentRadius = 0;

    for (let index = 0; index < lengthOfTransformed; index++) {
        let mirroredIndex = 2 * currentCenter - index;

        if (index < currentRadius)
            radiusArray[index] = Math.min(currentRadius - index, radiusArray[mirroredIndex]);

        while (
            index + 1 + radiusArray[index] < lengthOfTransformed &&
            index - 1 - radiusArray[index] >= 0 &&
            transformedString.charAt(index + 1 + radiusArray[index]) ==
                transformedString.charAt(index - 1 - radiusArray[index])
        )
            radiusArray[index]++;

        if (index + radiusArray[index] > currentRadius) {
            currentCenter = index;
            currentRadius = index + radiusArray[index];
        }
    }

    let maxRadius = 0;
    let indexAtMaxRadius = 0;
    for (let i = 0; i < lengthOfTransformed; i++) {
        if (radiusArray[i] > maxRadius) {
            maxRadius = radiusArray[i];
            indexAtMaxRadius = i;
        }
    }

    let startOfLongestPalindrome = Math.floor((indexAtMaxRadius - maxRadius) / 2);
    let resultLongestPalindrome = stringInput.slice(startOfLongestPalindrome, startOfLongestPalindrome + maxRadius);

    return resultLongestPalindrome;
};

The JavaScript function findLongestPalindrome effectively computes the longest palindromic substring found within a given string. The process leverages a transformative approach that involves working with an augmented version of the original string, facilitating a straightforward palindrome detection.

  • The initial step introduces symbols between characters and at the extremities of the input string. This conversion ensures that palindromes of both even and odd lengths can be uniformly handled as odd-length palindromes.
  • An array radiusArray is utilized to store the maximum radius of parity from each position in the transformed string during the exploration.
  • Central variables, currentCenter and currentRadius, are adjusted dynamically with each expansion to efficiently manage and keep track of the current palindrome's center and boundaries.
  • A mirrored calculation strategy helps optimize each radius expansion by reusing previously calculated results, hence speeding up the process.
  • After successfully identifying potential centers and their corresponding radii, the function detects the longest palindrome by selecting the maximum value in radiusArray.
  • The start index of the substring in the original input string is recalculated without the added characters, and the actual longest palindrome is extracted and returned.

This function provides an efficient solution to the palindrome identification problem by leveraging a modified string and radius expansion technique to handle substrings systematically. It offers a complexity that is generally more manageable compared to simplistic brute force approaches.

python
class Solution:
    def findLongestPalindrome(self, input_string: str) -> str:
        modified_string = "#" + "#".join(input_string) + "#"
        length = len(modified_string)
        palindrome_lengths = [0] * length
        current_center = current_radius = 0

        for i in range(length):
            reflection = 2 * current_center - i

            if i < current_radius:
                palindrome_lengths[i] = min(current_radius - i, palindrome_lengths[reflection])

            while (
                i + 1 + palindrome_lengths[i] < length
                and i - 1 - palindrome_lengths[i] >= 0
                and modified_string[i + 1 + palindrome_lengths[i]]
                == modified_string[i - 1 - palindrome_lengths[i]]
            ):
                palindrome_lengths[i] += 1

            if i + palindrome_lengths[i] > current_radius:
                current_center = i
                current_radius = i + palindrome_lengths[i]

        max_len = max(palindrome_lengths)
        center_pos = palindrome_lengths.index(max_len)
        initial_pos = (center_pos - max_len) // 2
        result_palindrome = input_string[initial_pos : initial_pos + max_len]

        return result_palindrome

The provided Python code defines a solution for finding the longest palindromic substring within a given string. The method findLongestPalindrome efficiently determines the longest sequence of characters that reads the same forwards and backwards. Here's a concise overview of how the algorithm functions:

  • Initialize a modified version of the input string to include hash (#) characters. These act as boundaries, preventing index overflow and aiding in center expansion checks.
  • Create and populate an array to track the lengths of potential palindromes around each character (or hash) in the modified string.
  • Use two pointers, current_center and current_radius, to hold the center and the radius (length) of the current known largest palindrome.
  • Utilize the characteristics of palindromes around the center to efficiently calculate possible palindromic lengths.
    • If the current index is within the radius of the current largest palindrome, utilize its symmetric property.
    • Expand the palindrome from the current center outwards, checking for matching characters.
    • Update the current_center and current_radius if the newly found palindrome is larger.
  • After traversing the string, identify the maximum palindrome length and its position.
  • Extract and return the longest palindromic substring from the original input string based on calculations from the modified string.

This algorithm leverages symmetrical properties of palindromes to enhance efficiency, avoiding the naive approach which requires checking each substring one by one. The user of this code can thus expect a function optimized for faster execution and lower computational overhead when determining palindromic sequences.

Comments

No comments yet.