Longest Palindromic Substring Explained | Brute Force, Dynamic Programming, Expand Around Center & Manacher's Algorithm (C++)

1. Introduction

String manipulation and parsing are foundational elements of backend system design, data validation, and text processing pipelines. Among the classic string algorithms, finding the "Longest Palindromic Substring" (often encountered as LeetCode 5) stands out as a quintessential test of algorithmic thinking.

For highly competitive Software Development Engineer 1 (SDE 1) online assessments, this problem acts as a crucial gatekeeper. It doesn't just test if you can find the right answer; it evaluates how efficiently you can optimize your logic. Interviewers use this problem to observe your progression from a naive approach to an optimal, production-ready solution that minimizes memory allocation—a critical skill for robust backend engineering.

A palindrome is a string that reads the same forwards and backwards (like "racecar" or "madam"). Finding the longest one within a larger string has real-world analogs in computational biology (DNA sequence analysis), data compression, and cryptography. In this comprehensive guide, we will break down the mechanics of the problem, gradually stripping away inefficiencies until we arrive at the optimal solution.

2. Problem Statement

Description

Given a string $s$, return the longest palindromic substring in $s$. A substring is a contiguous non-empty sequence of characters within a string.

Input

• A single string $s$ consisting of digits and English letters.

Output

• A string representing the longest contiguous palindromic sequence.

Constraints

• $1 \le s.length \le 1000$
• $s$ consists of only digits and English letters.

Example 1

Input: s = "babad"

Output: "bab"

(Note: "aba" is also a valid answer and is equally acceptable).

Example 2

Input: s = "cbbd"

Output: "bb"

Approach 1: Brute Force

Intuition

The most straightforward way to solve this problem is to generate every possible substring of the given string and check if each one is a palindrome. If it is, we compare its length to our longest recorded palindrome and update our record if the current one is longer.

This approach mimics human trial-and-error but lacks the systemic efficiency required for large-scale data.

Algorithm

1. Initialize a variable maxLength to 0 and a string longestStr to hold the result.
2. Use two nested loops to generate all possible starting indices $i$ and ending indices $j$ of substrings.
3. For every substring $s[i \dots j]$, use a helper function to verify if it is a palindrome.
4. The helper function uses two pointers (one at the start, one at the end), moving inwards and comparing characters.
5. If the substring is a palindrome and its length $(j - i + 1)$ is greater than maxLength, update maxLength and longestStr.

Dry Run

Let's dry run the string s = "babad".

C++ Code

#include <iostream>
#include <string>

using namespace std;

class Solution {
private:
    // Helper function to check whether
    // the substring s[left...right] is a palindrome
    bool isPalindrome(const string& s, int left, int right) {

        // Compare characters from both ends
        while (left < right) {

            // If characters don't match,
            // it is not a palindrome
            if (s[left] != s[right]) {
                return false;
            }

            // Move towards the center
            left++;
            right--;
        }

        // All characters matched
        return true;
    }

public:
    string longestPalindrome(string s) {

        // Length of the input string
        int n = s.length();

        // If the string has 0 or 1 character,
        // it is already a palindrome
        if (n <= 1)
            return s;

        // Stores the longest palindrome found so far
        string longestStr = "";

        // Stores the length of the longest palindrome
        int maxLength = 0;

        // Try every possible starting index
        for (int i = 0; i < n; i++) {

            // Try every possible ending index
            // starting from i
            for (int j = i; j < n; j++) {

                // Check whether the current substring
                // s[i...j] is a palindrome
                if (isPalindrome(s, i, j)) {

                    // Calculate its length
                    int currentLength = j - i + 1;

                    // If this palindrome is longer than
                    // the previous best one, update the answer
                    if (currentLength > maxLength) {
                        maxLength = currentLength;

                        // Extract the palindrome substring
                        longestStr = s.substr(i, currentLength);
                    }
                }
            }
        }

        // Return the longest palindromic substring
        return longestStr;
    }
};

Complexity Analysis

• Time Complexity: $O(n^3)$. Generating all substrings takes $O(n^2)$ time. For each substring, checking if it is a palindrome takes $O(n)$ time. $O(n^2) \times O(n) = O(n^3)$.
• Space Complexity: $O(1)$. We only use a few variables for tracking indices and lengths, requiring constant extra space (excluding the space needed for the output string).

Why This Approach Is Inefficient

While logically sound, $O(n^3)$ operations will result in a Time Limit Exceeded (TLE) error for strings approaching lengths of 1000 characters. We are repeatedly checking the same inner substrings. For example, to check if "ababa" is a palindrome, we check if the outer 'a's match, and then we check if "bab" is a palindrome. But we likely already checked "bab" in a previous iteration! This overlapping computation is a glaring inefficiency.

Approach 2: The "Reverse and Compare" Trap (Intermediate)

Intuition

Before reaching the optimal solutions, many candidates attempt to reverse the original string $s$ to create $s'$ and then find the Longest Common Substring between $s$ and $s'$.

Algorithm Outline

1. Reverse $s$ to get $s'$.
2. Use standard dynamic programming to find the longest common substring between the two.

Limitations & Why We Skip It

This sounds elegant, but there is a massive trap here.

Consider s = "abacdfgdcaba" and its reverse s' = "abacdgfdcaba".

The longest common substring between them is "abacd". However, "abacd" is not a palindrome!

To make this approach work, whenever a common substring is found, you must verify that the indices of the matched characters correspond to the original string's exact mirrored positions. This requires an extra $O(1)$ index check. While it brings the time down to $O(n^2)$, the setup is overly complex and requires $O(n^2)$ space for the Longest Common Substring DP table.

Because of these pitfalls, we explicitly bypass this intermediate step and move to a much safer, native Dynamic Programming approach.

Approach 3: Dynamic Programming

Intuition

To eliminate the redundant checks from our Brute Force approach, we can cache our previous findings. This introduces Dynamic Programming (DP).

The core realization is that a string is a palindrome if:

1. Its first and last characters are identical.
2. The remaining inner substring is also a palindrome.

For instance, the string "cabac" is a palindrome because the outer characters 'c' and 'c' match, and the inner string "aba" is already known to be a palindrome.

DP State

Let $dp[i][j]$ be a boolean table where $dp[i][j] = \text{true}$ if the substring $s[i \dots j]$ is a palindrome, and $\text{false}$ otherwise.

Transition

$dp[i][j] = (s[i] == s[j]) \text{ and } dp[i+1][j-1]$

Base Cases

1. Length 1: Every single character is a palindrome.$dp[i][i] = \text{true}$
2. Length 2: Two characters form a palindrome if they are identical.$dp[i][i+1] = (s[i] == s[i+1])$

Algorithm

1. Create an $n \times n$ boolean matrix initialized to false.
2. Fill all $dp[i][i]$ with true.
3. Check all substrings of length 2.
4. Iterate through substring lengths from 3 up to $n$.
5. For each length, iterate through all valid starting positions $i$. Calculate the ending position $j$.
6. Apply the state transition equation.
7. Keep track of the maximum length and the starting index to construct the final string.

Dry Run

Input: s = "babad"

Base Case (Length 1):

• $dp[0][0], dp[1][1], dp[2][2], dp[3][3], dp[4][4]$ are all true.

Base Case (Length 2):

• s[0..1] = "ba" $\rightarrow$ $dp[0][1] = \text{false}$
• s[1..2] = "ab" $\rightarrow$ $dp[1][2] = \text{false}$
• s[2..3] = "ba" $\rightarrow$ $dp[2][3] = \text{false}$

Length 3:

• s[0..2] = "bab" $\rightarrow$ $s[0] == s[2]$ ('b' == 'b') and $dp[1][1]$ is true. $dp[0][2] = \text{true}$. (Longest = 3)
• s[1..3] = "aba" $\rightarrow$ $s[1] == s[3]$ ('a' == 'a') and $dp[2][2]$ is true. $dp[1][3] = \text{true}$.

C++ Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {

        // Length of the input string
        int n = s.length();

        // If the string has 0 or 1 character,
        // it is already a palindrome
        if (n <= 1)
            return s;

        // dp[i][j] = true if substring s[i...j]
        // is a palindrome
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        // Starting index of the longest palindrome
        int start = 0;

        // Length of the longest palindrome
        int maxLength = 1;

        // -------------------------------
        // Base Case 1:
        // Every single character is
        // a palindrome of length 1
        // -------------------------------
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // -------------------------------
        // Base Case 2:
        // Check all substrings of length 2
        // -------------------------------
        for (int i = 0; i < n - 1; i++) {

            // Two-character substring is a palindrome
            // only if both characters are equal
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;

                // Update the longest palindrome found
                start = i;
                maxLength = 2;
            }
        }

        // -----------------------------------------
        // Check substrings of length 3 to n
        // -----------------------------------------
        for (int len = 3; len <= n; len++) {

            // Iterate over every possible
            // starting index
            for (int i = 0; i < n - len + 1; i++) {

                // Compute the ending index
                int j = i + len - 1;

                // A substring is a palindrome if:
                // 1. First and last characters match
                // 2. The inner substring is already
                //    known to be a palindrome
                if (s[i] == s[j] && dp[i + 1][j - 1]) {

                    // Mark current substring as palindrome
                    dp[i][j] = true;

                    // If it is the longest palindrome
                    // found so far, update the answer
                    if (len > maxLength) {
                        start = i;
                        maxLength = len;
                    }
                }
            }
        }

        // Return the longest palindromic substring
        return s.substr(start, maxLength);
    }
};

Complexity Analysis

• Time Complexity: $O(n^2)$. We fill an $n \times n$ matrix where each lookup takes $O(1)$ time.
• Space Complexity: $O(n^2)$. We allocate a 2D boolean array of size $n \times n$.

Advantages and Disadvantages

• Advantages: Solves the overlapping subproblems issue, reducing time complexity from $O(n^3)$ to $O(n^2)$. The logic is highly declarative and easy to trace.
• Disadvantages: Space complexity is heavy. In a modern backend environment, allocating an $O(n^2)$ matrix for a string parsing utility is poor practice. If the string has 10,000 characters, we are allocating a massive 100,000,000-cell array just to check string bounds. There is an algorithm that maintains the $O(n^2)$ time but drastically reduces space to $O(1)$.

Approach 4: Expand Around Center (Optimal Interview Solution)

Intuition

Every palindrome mirrors around its center. Instead of checking the boundaries and looking inwards, what if we choose a center point and expand outwards?

Since a palindrome mirrors around its center, we can try treating every character (and every space between characters) as a potential center and expand pointers outwards as long as the characters match.

Center Types:

1. Odd-length palindromes have a distinct single character as the center. (e.g., in "aba", the center is 'b').
2. Even-length palindromes have the space between two identical characters as the center. (e.g., in "abba", the center is between the two 'b's).

For a string of length $n$, there are $n$ single-character centers and $n-1$ space-between-character centers, resulting in $2n - 1$ total possible centers. Expanding from all $2n - 1$ centers ensures we find every single palindrome without needing a massive 2D matrix.

Visualizing Expansion

Algorithm

1. Initialize start and maxLength variables.
2. Loop through the string, treating every index $i$ as a potential center.
3. For each index, call a helper function expandAroundCenter twice:
   • Once for an odd-length palindrome (center is $i$, left = $i$, right = $i$).
   • Once for an even-length palindrome (center is between $i$ and $i+1$, left = $i$, right = $i+1$).
4. The helper function expands left and right pointers as long as characters match and boundaries are valid. It returns the length of the palindrome found.
5. Take the maximum length found from both the odd and even expansion.
6. If this length is greater than the current maxLength, update start and maxLength based on index offsets.

Dry Run

Input: s = "babad"

Result: "bab" (starting from index 0, length 3).

C++ Code

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
private:
    // Expands around the given center and
    // returns the length of the palindrome
    int expandAroundCenter(const string& s, int left, int right) {

        // Keep expanding as long as:
        // 1. Indices are within bounds
        // 2. Characters on both sides are equal
        while (left >= 0 &&
               right < s.length() &&
               s[left] == s[right]) {

            // Expand one step outward
            left--;
            right++;
        }

        // The loop stops after expanding one step too far,
        // so subtract 1 from both sides to get
        // the actual palindrome length
        return right - left - 1;
    }

public:
    string longestPalindrome(string s) {

        // Empty string has no palindrome
        if (s.empty())
            return "";

        // Starting index of the longest palindrome
        int start = 0;

        // Length of the longest palindrome
        int maxLength = 0;

        // Treat every index as a possible center
        for (int i = 0; i < s.length(); i++) {

            // -------------------------------
            // Case 1:
            // Odd-length palindrome
            // Center = one character
            // Example: "racecar"
            //            ^
            // -------------------------------
            int len1 = expandAroundCenter(s, i, i);

            // -------------------------------
            // Case 2:
            // Even-length palindrome
            // Center = between two characters
            // Example: "abba"
            //             ^
            // -------------------------------
            int len2 = expandAroundCenter(s, i, i + 1);

            // Choose the longer palindrome
            // found from the two centers
            int len = max(len1, len2);

            // Update the answer if a longer
            // palindrome is found
            if (len > maxLength) {

                // Compute the starting index
                // of the palindrome
                //
                // Formula:
                // start = center - (length - 1) / 2
                //
                // Works correctly for both
                // odd and even length palindromes
                start = i - (len - 1) / 2;

                // Store the new maximum length
                maxLength = len;
            }
        }

        // Return the longest palindromic substring
        return s.substr(start, maxLength);
    }
}

Complexity Analysis

• Time Complexity: $O(n^2)$. Expanding around $2n - 1$ centers takes $O(n)$ time in the worst-case scenario (e.g., if the string is entirely identical characters like "aaaaa").
• Space Complexity: $O(1)$. We only use a few integer variables, avoiding the massive $O(n^2)$ spatial footprint of Dynamic Programming.

Why This Is Better Than DP

When facing rigorous online assessments that measure computational efficiency against stringent test cases, $O(n^2)$ time with $O(1)$ space is the expected standard. It demonstrates you understand core data structure efficiencies—namely, avoiding state arrays when inline variables can accomplish the task mathematically.

Approach 5: Manacher's Algorithm (Advanced)

Introduction

While the Expand Around Center approach satisfies almost all interview requirements, there exists a legendary algorithm that pushes the boundaries of theoretical optimization. Invented by Glenn K. Manacher in 1975, this algorithm finds the longest palindromic substring in strictly $O(n)$ time.

Core Idea

Manacher's Algorithm achieves linear time by intelligently reusing previously computed palindrome lengths, completely avoiding redundant expansions.

To handle both odd and even length palindromes elegantly, Manacher's first preprocesses the string by inserting special delimiter characters (like #) between every letter, as well as distinct boundary markers at the ends.

"babad" becomes "$#b#a#b#a#d#@"

The Three Pillars of Manacher's:

1. The Array $P[i]$: Stores the "palindrome radius" at each center $i$.
2. Center $(C)$ and Right Boundary $(R)$: We keep track of the palindrome that extends furthest to the right. $C$ is its center, and $R$ is its rightmost character index.
3. Mirror Index: When we move to a new center $i$ that is within the right boundary $R$ (i.e., $i < R$), we can find its mirror index on the left side of $C$, called $i_{mirror}$. We initialize $P[i]$ to $P[i_{mirror}]$, dramatically skipping redundant expansions!

Algorithm

1. Transform $s$ into $T$ with # boundaries to unify even/odd logic.
2. Initialize array $P$ of the same length as $T$ to store radii.
3. Iterate $i$ through $T$.
4. If $i < R$, the current index is inside a known palindrome. Set $P[i]$ to the minimum of $R - i$ and $P[i_{mirror}]$.
5. Expand outward from $i$ using normal checks, incrementing $P[i]$ for matches.
6. If the new palindrome centered at $i$ expands past $R$, update $C = i$ and $R = i + P[i]$.
7. Track the maximum value in $P$ to find the longest palindrome.

C++ Code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
private:

    // Preprocess the string by inserting '#'
    // between every character and adding
    // boundary characters '^' and '$'
    //
    // Example:
    // "abba" -> "^#a#b#b#a#$"
    //
    // This converts both odd and even length
    // palindromes into a single odd-length format.
    string preProcess(const string& s) {

        // Handle empty string
        if (s.empty())
            return "^$";

        string ret = "^";

        // Insert '#' between every character
        for (char c : s) {
            ret += "#" + string(1, c);
        }

        // Add trailing separator and ending boundary
        ret += "#$";

        return ret;
    }

public:
    string longestPalindrome(string s) {

        // Preprocessed string
        string T = preProcess(s);

        // Length of transformed string
        int n = T.length();

        // P[i] stores the radius of the palindrome
        // centered at index i
        vector<int> P(n, 0);

        // C = Current center of the rightmost palindrome
        // R = Right boundary of that palindrome
        int C = 0, R = 0;

        // Track the longest palindrome found
        int maxLen = 0;
        int centerIndex = 0;

        // Iterate through every possible center
        // except the two boundary characters
        for (int i = 1; i < n - 1; i++) {

            // Mirror position of i with respect
            // to the current center C
            int i_mirror = 2 * C - i;

            // If i lies inside the current
            // right boundary, use the mirror's
            // palindrome information to avoid
            // unnecessary comparisons
            if (R > i) {
                P[i] = min(R - i, P[i_mirror]);
            }

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

            // If the palindrome centered at i
            // extends beyond the current right
            // boundary, update C and R
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }

            // Update the longest palindrome
            // found so far
            if (P[i] > maxLen) {
                maxLen = P[i];
                centerIndex = i;
            }
        }

        // Convert the center position in the
        // transformed string back to the
        // starting index in the original string
        int start = (centerIndex - 1 - maxLen) / 2;

        // Return the longest palindromic substring
        return s.substr(start, maxLen);
    }
};

Complexity Analysis

• Time Complexity: $O(n)$. Even with the inner while loop, the right boundary $R$ only ever moves rightwards. It can move right at most $2n$ times. Therefore, the amortized time complexity is strictly linear.
• Space Complexity: $O(n)$ to store the preprocessed string $T$ and the radius array $P$.

When To Use

Manacher's Algorithm is a marvel of computer science but is rarely expected in standard SDE 1 interviews due to its intricate implementation. However, for competitive programming, coding club hackathons, or environments where massive strings need instantaneous validation, Manacher's is an ace up the sleeve that differentiates exceptional logic from standard solutions.

Correctness Proof (Expand Around Center)

To prove that Expand Around Center finds the absolute longest palindrome, we rely on the foundational definition: every palindrome must have exactly one geometric center.

• If a palindrome has an odd length, its geometric center is a single distinct character.
• If a palindrome has an even length, its geometric center falls perfectly between two characters.

Because our algorithm systematically treats every character (and every space between characters) as a potential center and expands to the absolute maximum mathematical boundary for that specific center, it is impossible for a valid palindromic sequence to be missed. The global maximum is simply extracted from these local maximums.

Edge Cases to Consider

When writing backend logic for parsing, robust code handles edge cases gracefully:

1. Empty String: Returns an empty string immediately.
2. Single Character (s = "a"): Returns the character itself. The loops handle this, but an early return if (s.length() <= 1) prevents unnecessary operations.
3. Entire String is Palindrome (s = "racecar"): The algorithm will expand from the exact middle out to the boundaries correctly.
4. Repeated Characters (s = "aaaaa"): This is the worst-case scenario for the Expand Around Center approach (triggering maximum $O(n^2)$ expansions), but it still runs efficiently within time limits.

Common Mistakes

1. Off-by-One Errors in Substring Extraction:In C++, s.substr(start, length) expects the starting index and the length. A common mistake is passing the ending index instead of the length.
2. Forgetting Even-Length Centers:Candidates often write the logic to expand around single characters expand(s, i, i) but completely forget to check between characters expand(s, i, i+1), missing all even-length palindromes like "abba".
3. Boundaries Checking:Failing to check left >= 0 and right < s.length() before comparing s[left] == s[right] will trigger out-of-bounds memory access errors.

Interview Tips

• Vocalize the Inefficiencies: If an interviewer presents this problem, do not immediately code the $O(1)$ space solution. State the brute force, explain why it overlaps (the $O(n^3)$ problem), and then transition to Expand Around Center.
• Master the Mathematical Offsets: The line start = i - (len - 1) / 2; in the Expand approach often confuses candidates under pressure. Practice deriving this by drawing it out on a whiteboard or paper. If len = 4 and center index $i$ is 1 (the left character of the middle pair), start becomes 1 - (4-1)/2 = 0.
• Understand the Follow-Ups: Interviewers may ask, "How would you modify this to find the number of palindromic substrings instead of the longest?" (LeetCode 647). The Expand Around Center logic handles this perfectly—just count the expansions instead of recording max length!

Key Takeaways

1. Evolution of Logic: The journey from Brute Force to Expand Around Center showcases the importance of removing redundant operations. We moved from generating unrelated substrings to expanding structurally valid boundaries.
2. Best for Interviews: The Expand Around Center approach ($O(n^2)$ time, $O(1)$ space) is the golden standard. It perfectly balances clean readability with optimal memory constraints, exactly what logic-driven backend architectures demand.
3. Best for Competitive Programming: Manacher's Algorithm ($O(n)$ time) is the ultimate mathematical weapon for extreme constraints, though its intricate array manipulations make it prone to typos in a 45-minute technical screen.

FAQ

1. Why don't we use Dynamic Programming as the primary solution?

While DP is an excellent paradigm, allocating an $n \times n$ matrix for string comparison requires $O(n^2)$ space. For a string of length 1000, this requires a million boolean checks. The "Expand Around Center" method operates in the same time complexity but requires essentially zero extra memory.

2. Does checking odd and even length centers double the time complexity?

It increases the constant factor (checking $2n - 1$ centers instead of $n$), but in Big-O notation, $2n$ is still $O(n)$. The worst-case runtime remains bounded strictly by $O(n^2)$.

3. Can I use recursion instead of iteration for the Expand approach?

Yes, you can write the expandAroundCenter helper recursively. However, iteration (while loop) is heavily preferred as it prevents stack overflow errors on massively long palindromes.

4. Why are # symbols inserted in Manacher's Algorithm?

The # symbols normalize the string. By forcing an artificial character between every actual character, all palindromes mathematically become odd-length (having a defined, single # or letter as a center), allowing a single unified loop logic.

5. What if there are multiple longest palindromic substrings of the same length?

The problem only requires you to return any one of them. In the Expand Around Center code, we only update maxLength if the new length is strictly greater (>), meaning it returns the first one encountered. Changing it to >= would return the last one encountered. Both are perfectly valid.

code link:

https://leetcode.com/problems/longest-palindromic-substring/description/

reference video link: