Skip to main content
CodePeetCodePeet
BLIND 75

Longest Palindromic Substring

MEDIUMProblemSolveExternal Links

Description

You are given a string s consisting of letters and digits. Your task is to find and return the longest substring within s that forms a palindrome.

A palindrome is a sequence of characters that reads the same when traversed from left to right as when traversed from right to left. For example, "radar", "level", and "121" are all palindromes.

A substring is a contiguous sequence of characters within a string. For instance, given the string "hello", the substrings include "h", "he", "hel", "ell", "llo", "lo", "o", and so on.

If there are multiple palindromic substrings of the same maximum length, you may return any one of them.

Examples

Example 1

Input: s = "babad"

Output: "bab"

Explanation: In the string "babad", we need to find the longest palindrome. Let's examine the substrings:

  • Single characters: "b", "a", "b", "a", "d" are all palindromes of length 1
  • Length 2: "ba", "ab", "ba", "ad" - none are palindromes
  • Length 3: "bab" reads same forward and backward ✓, "aba" also reads same ✓
  • Length 4: "baba", "abad" - neither are palindromes
  • Length 5: "babad" - not a palindrome

The longest palindromic substrings are "bab" and "aba", both of length 3. Either answer is acceptable, so we return "bab".

Example 2

Input: s = "cbbd"

Output: "bb"

Explanation: Looking at all substrings of "cbbd":

  • Single characters: "c", "b", "b", "d" are palindromes of length 1
  • Length 2: "cb" (not palindrome), "bb" (palindrome! ✓), "bd" (not palindrome)
  • Length 3: "cbb", "bbd" - neither are palindromes
  • Length 4: "cbbd" - not a palindrome

The longest palindrome is "bb" with length 2.

Example 3

Input: s = "a"

Output: "a"

Explanation: When the string has only one character, that single character is itself the longest palindrome. Every single character is a palindrome by definition since it reads the same in both directions.

Example 4

Input: s = "forgeeksskeegfor"

Output: "geeksskeeg"

Explanation: This example contains a longer palindrome embedded within the string. The substring "geeksskeeg" is a palindrome of length 10:

  • Reading forward: g-e-e-k-s-s-k-e-e-g
  • Reading backward: g-e-e-k-s-s-k-e-e-g

Both readings are identical, confirming it's a palindrome. This is the longest such substring in the given string.

Constraints

  • 1 ≤ s.length ≤ 1000
  • s consists only of digits (0-9) and English letters (a-z, A-Z)

Editorial

Brute Force

Intuition

The most straightforward approach is to consider every possible substring of the given string and check whether each one is a palindrome. We keep track of the longest palindrome found during this process.

Think of it like manually checking every possible contiguous portion of the string. For the string "babad", we would check:

  • All substrings starting at index 0: "b", "ba", "bab", "baba", "babad"
  • All substrings starting at index 1: "a", "ab", "aba", "abad"
  • All substrings starting at index 2: "b", "ba", "bad"
  • And so on...

For each substring, we verify if it reads the same forwards and backwards. This is the most intuitive solution that a beginner would think of.

Step-by-Step Explanation

Let's trace through with s = "babad":

Step 1: Initialize variables

  • longest_start = 0 (starting index of longest palindrome found)
  • max_length = 1 (length of longest palindrome, at minimum any single char is a palindrome)

Step 2: Generate all substrings using two nested loops

  • Outer loop (i): starting index from 0 to n-1
  • Inner loop (j): ending index from i to n-1

Step 3: For each substring s[i..j], check if it's a palindrome by comparing characters from both ends:

i=0, j=0: substring = "b"
  Is "b" palindrome? Yes (single char). Length = 1.

i=0, j=2: substring = "bab"
  Compare s[0]='b' with s[2]='b'. Match!
  Compare s[1]='a' with s[1]='a'. Match! (middle)
  Yes, palindrome! Length = 3 > 1, update: start=0, max_length=3

i=0, j=3: substring = "baba"
  Compare s[0]='b' with s[3]='a'. No match. Not a palindrome.

i=1, j=3: substring = "aba"
  Compare s[1]='a' with s[3]='a'. Match!
  Compare s[2]='b' with s[2]='b'. Match! (middle)
  Palindrome! Length = 3 = max_length, no update needed.

Result: s[0:3] = "bab"

Algorithm

  1. Initialize start = 0 and maxLen = 1 to track the longest palindrome found
  2. For each starting index i from 0 to n-1:
    • For each ending index j from i to n-1:
      • Extract substring s[i..j]
      • Check if this substring is a palindrome by comparing characters from both ends moving inward
      • If it is a palindrome and its length > maxLen:
        • Update start = i and maxLen = j - i + 1
  3. Return the substring from index start with length maxLen

Code

#include <string>
using namespace std;

class Solution {
public:
    bool isPalindrome(const string& s, int low, int high) {
        while (low < high) {
            if (s[low] != s[high]) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
    
    string longestPalindrome(string s) {
        int n = s.length();
        if (n == 0) return "";
        
        int start = 0;
        int maxLen = 1;
        
        // Generate all substrings
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check if substring s[i..j] is a palindrome
                if (isPalindrome(s, i, j)) {
                    int currLen = j - i + 1;
                    if (currLen > maxLen) {
                        start = i;
                        maxLen = currLen;
                    }
                }
            }
        }
        
        return s.substr(start, maxLen);
    }
};
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""
        
        def is_palindrome(low: int, high: int) -> bool:
            """Check if substring s[low..high] is a palindrome"""
            while low < high:
                if s[low] != s[high]:
                    return False
                low += 1
                high -= 1
            return True
        
        start = 0
        max_len = 1
        
        # Generate all substrings
        for i in range(n):
            for j in range(i, n):
                # Check if substring s[i..j] is a palindrome
                if is_palindrome(i, j):
                    curr_len = j - i + 1
                    if curr_len > max_len:
                        start = i
                        max_len = curr_len
        
        return s[start:start + max_len]
class Solution {
    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low) != s.charAt(high)) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
    
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";
        
        int start = 0;
        int maxLen = 1;
        
        // Generate all substrings
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check if substring s[i..j] is a palindrome
                if (isPalindrome(s, i, j)) {
                    int currLen = j - i + 1;
                    if (currLen > maxLen) {
                        start = i;
                        maxLen = currLen;
                    }
                }
            }
        }
        
        return s.substring(start, start + maxLen);
    }
}

Complexity Analysis

Time Complexity: O(n³)

We have three nested operations:

  1. The outer loop runs n times (for each starting position)
  2. The inner loop runs up to n times (for each ending position)
  3. The palindrome check takes O(n) time in the worst case (comparing characters from both ends)

Total: n × n × n = O(n³)

Space Complexity: O(1)

We only use a constant amount of extra space for variables like start, maxLen, low, and high. No additional data structures that grow with input size are used.

Why This Approach Is Not Efficient

The brute force approach has O(n³) time complexity. Given the constraint that n can be up to 1000:

  • Worst case operations: 1000³ = 1,000,000,000 (one billion) operations
  • This would take approximately 10-100 seconds on typical hardware
  • Most competitive programming judges have time limits of 1-2 seconds

The inefficiency comes from two sources:

  1. We generate all possible substrings: O(n²) pairs
  2. For each substring, we independently verify if it's a palindrome: O(n) per check

Key Insight for Improvement: We're doing redundant work. If we know that "aba" is a palindrome, and the characters on both sides are equal (say 'x'), then "xabax" must also be a palindrome. We can use this observation to avoid rechecking overlapping portions of the string.

Better Approach - Dynamic Programming

Intuition

The key insight that leads to dynamic programming is recognizing a pattern in how palindromes are structured:

Core Observation: A string is a palindrome if:

  1. Its first and last characters are the same, AND
  2. The substring between them (excluding first and last) is also a palindrome

For example:

  • Is "xabax" a palindrome?

    • First char 'x' == Last char 'x'? Yes ✓
    • Is inner part "aba" a palindrome? Yes ✓
    • Therefore, "xabax" is a palindrome!

  • Is "xabay" a palindrome?

    • First char 'x' != Last char 'y'. No ✗
    • No need to check further.

This recursive structure is perfect for dynamic programming. We can build a 2D table where dp[i][j] stores whether the substring from index i to index j is a palindrome. We fill this table starting from smaller substrings and work our way up to longer ones, reusing previously computed results.

Step-by-Step Explanation

Let's trace through with s = "babad" (length n = 5):

Step 1: Create a 5×5 boolean DP table, initialized to false

Step 2: Base case - All single characters are palindromes (length 1)

  • Set dp[i][i] = true for all i. max_length = 1, start = 0

Step 3: Check substrings of length 2

  • s[0]='b' vs s[1]='a' → different → dp[0][1] = false
  • s[1]='a' vs s[2]='b' → different → dp[1][2] = false
  • s[2]='b' vs s[3]='a' → different → dp[2][3] = false
  • s[3]='a' vs s[4]='d' → different → dp[3][4] = false

Step 4: Check substrings of length 3

  • i=0, j=2: s[0]='b' == s[2]='b'? Yes! Inner dp[1][1] = true. dp[0][2] = true ✓ → "bab" palindrome! Update: start=0, max_length=3
  • i=1, j=3: s[1]='a' == s[3]='a'? Yes! Inner dp[2][2] = true. dp[1][3] = true ✓ → "aba" palindrome!
  • i=2, j=4: s[2]='b' == s[4]='d'? No. dp[2][4] = false

Step 5: Length 4 and 5 → no palindromes found

Result: s[0:3] = "bab"

DP Table Construction — Building Palindrome Knowledge — Watch how the 2D DP table is filled diagonally, starting with single characters (trivially palindromes), then length-2, then length-3 substrings. Each cell dp[i][j] reuses the result of dp[i+1][j-1] to avoid redundant palindrome checks.

Algorithm

  1. Create a 2D boolean array dp[n][n] where dp[i][j] indicates if s[i..j] is a palindrome
  2. Initialize: All single characters are palindromes → dp[i][i] = true
  3. Check length-2 substrings: dp[i][i+1] = (s[i] == s[i+1])
  4. For lengths from 3 to n:
    • For each starting position i (where ending j = i + len - 1 < n):
      • dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1]
      • If dp[i][j] is true and length > maxLen, update start and maxLen
  5. Return substring starting at start with length maxLen

Code

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n == 0) return "";
        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));
        
        int start = 0;
        int maxLen = 1;
        
        // Base case: all substrings of length 1 are palindromes
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // Check substrings of length 2
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }
        
        // Check substrings of length 3 and above
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (len > maxLen) {
                        start = i;
                        maxLen = len;
                    }
                }
            }
        }
        
        return s.substr(start, maxLen);
    }
};
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""
        if n == 1:
            return s
        
        # dp[i][j] = True if substring s[i..j] is a palindrome
        dp = [[False] * n for _ in range(n)]
        
        start = 0
        max_len = 1
        
        # Base case: all substrings of length 1 are palindromes
        for i in range(n):
            dp[i][i] = True
        
        # Check substrings of length 2
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_len = 2
        
        # Check substrings of length 3 and above
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        start = i
                        max_len = length
        
        return s[start:start + max_len]
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";
        if (n == 1) return s;
        
        boolean[][] dp = new boolean[n][n];
        
        int start = 0;
        int maxLen = 1;
        
        // Base case: all substrings of length 1 are palindromes
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // Check substrings of length 2
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }
        
        // Check substrings of length 3 and above
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (len > maxLen) {
                        start = i;
                        maxLen = len;
                    }
                }
            }
        }
        
        return s.substring(start, start + maxLen);
    }
}

Complexity Analysis

Time Complexity: O(n²)

We fill a 2D table of size n×n. Each cell computation is O(1) because we're just checking if two characters are equal and looking up a previously computed value in the DP table. This gives us O(n²) total operations.

Space Complexity: O(n²)

We use a 2D boolean array of size n×n to store the palindrome status of all substrings. This requires O(n²) additional space.

Why This Approach Is Not Efficient

While the Dynamic Programming approach reduces time complexity from O(n³) to O(n²), it introduces a significant space overhead of O(n²) for the DP table.

For n = 1000:

  • We need a table of size 1000 × 1000 = 1,000,000 boolean entries
  • This consumes approximately 1 MB of memory

The question arises: Can we achieve O(n²) time without the O(n²) space overhead?

The answer is yes. By changing our perspective from "build up from smaller palindromes" to "expand outward from potential centers," we can eliminate the need for the DP table entirely while maintaining the same time complexity.

Even Better Approach - Expand Around Center

Intuition

Instead of checking if each substring is a palindrome, let's think about palindromes from a different angle: every palindrome has a center.

Consider these palindromes:

  • "aba" has center at index 1 (the 'b')
  • "abba" has center between indices 1 and 2 (between the two 'b's)

This leads to a key insight:

  1. Odd-length palindromes have a single character as center
  2. Even-length palindromes have two adjacent characters as center

The Expansion Technique:
For each possible center position, we expand outward in both directions as long as the characters match. When they stop matching, we've found the longest palindrome with that center.

For a string of length n:

  • There are n possible centers for odd-length palindromes (each character)
  • There are n-1 possible centers for even-length palindromes (each gap between characters)
  • Total: 2n - 1 centers to check

This approach is more intuitive because it mimics how we might manually find palindromes: pick a center, then see how far the palindrome extends.

Step-by-Step Explanation

Let's trace through with s = "babad" (length n = 5):

Initialize: start = 0, maxLen = 1

For each index i, we try two expansions (odd-length and even-length):

i = 0 (character 'b'):

  • Odd-length (center = s[0]): "b" → try expand: left-1 = -1 (out of bounds). Stop. Length = 1
  • Even-length (between s[0] and s[1]): s[0]='b' vs s[1]='a' → not equal. No even palindrome.

i = 1 (character 'a'):

  • Odd-length (center = s[1]): "a" → expand: s[0]='b' vs s[2]='b' → equal! "bab" length=3 → expand: left-1=-1 out of bounds. Stop. Length = 3 > 1, update: start=0, maxLen=3
  • Even-length: s[1]='a' vs s[2]='b' → not equal. Stop.

i = 2 (character 'b'):

  • Odd-length: "b" → expand: s[1]='a' vs s[3]='a' → equal! "aba" length=3 → expand: s[0]='b' vs s[4]='d' → not equal. Stop. Length = 3 = maxLen (no update)
  • Even-length: s[2]='b' vs s[3]='a' → not equal. Stop.

i = 3, 4: Only length-1 palindromes.

Result: s[0:3] = "bab"

Expand Around Center — Growing Palindromes Outward — Watch how we try each character as a potential palindrome center and expand outward in both directions. When characters on both sides match, the palindrome grows. When they don't match, we move to the next center.

Algorithm

  1. Initialize start = 0 and maxLen = 1
  2. For each position i from 0 to n-1:
    a. Odd-length palindrome: Call expand(i, i) with same left and right
    b. Even-length palindrome: Call expand(i, i+1) with adjacent left and right
  3. The expand(left, right) function:
    • While left >= 0 AND right < n AND s[left] == s[right]:
      • Calculate current length = right - left + 1
      • If length > maxLen, update start and maxLen
      • Decrement left, increment right (expand outward)
  4. Return substring from start with length maxLen

Code

#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n == 0) return "";
        
        int start = 0;
        int maxLen = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 1; j++) {
                int left = i;
                int right = i + j;
                
                while (left >= 0 && right < n && s[left] == s[right]) {
                    int currLen = right - left + 1;
                    if (currLen > maxLen) {
                        start = left;
                        maxLen = currLen;
                    }
                    left--;
                    right++;
                }
            }
        }
        
        return s.substr(start, maxLen);
    }
};
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""
        
        start = 0
        max_len = 1
        
        def expand_around_center(left: int, right: int) -> None:
            nonlocal start, max_len
            
            while left >= 0 and right < n and s[left] == s[right]:
                curr_len = right - left + 1
                if curr_len > max_len:
                    start = left
                    max_len = curr_len
                left -= 1
                right += 1
        
        for i in range(n):
            # Odd-length palindrome: center at i
            expand_around_center(i, i)
            
            # Even-length palindrome: center between i and i+1
            expand_around_center(i, i + 1)
        
        return s[start:start + max_len]
class Solution {
    private int start = 0;
    private int maxLen = 1;
    
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";
        
        start = 0;
        maxLen = 1;
        
        for (int i = 0; i < n; i++) {
            expandAroundCenter(s, i, i);
            expandAroundCenter(s, i, i + 1);
        }
        
        return s.substring(start, start + maxLen);
    }
    
    private void expandAroundCenter(String s, int left, int right) {
        int n = s.length();
        
        while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
            int currLen = right - left + 1;
            if (currLen > maxLen) {
                start = left;
                maxLen = currLen;
            }
            left--;
            right++;
        }
    }
}

Complexity Analysis

Time Complexity: O(n²)

We iterate through each of the n positions in the string. For each position, we potentially expand outward up to n/2 times (in each direction). In the worst case (e.g., a string like "aaaa"), each expansion takes O(n) time. Since we do this for n positions: O(n) × O(n) = O(n²).

However, on average, most expansions terminate quickly, making this approach faster in practice than the DP solution despite having the same big-O complexity.

Space Complexity: O(1)

We only use a constant number of variables (start, maxLen, left, right). No additional data structures are needed. This is a significant improvement over the O(n²) space of the DP approach.

Why This Approach Is Not Efficient

The Expand Around Center approach achieves O(n²) time with O(1) space, which is excellent for most practical purposes. However, for very large strings (n approaching 10⁶ or more), even O(n²) can be too slow.

With n = 1000 (our constraint), we perform up to 1,000,000 operations, which is acceptable. But the question remains: Is there a way to solve this in linear time O(n)?

The redundancy in our current approach is that palindromes often overlap. If we've already found that a long palindrome exists at one location, we might be able to use that information to skip some checks at nearby locations.

This insight leads to Manacher's Algorithm, which cleverly reuses information about previously found palindromes to achieve O(n) time complexity.

Optimal Approach - Manacher's Algorithm

Intuition

Manacher's Algorithm is a sophisticated technique that finds the longest palindromic substring in linear time. The key insights are:

1. String Transformation:
To handle both odd and even length palindromes uniformly, we insert a special character (like '#') between every character and at the boundaries. For example:

  • "babad" becomes "#b#a#b#a#d#"
  • Now ALL palindromes are odd-length in the transformed string!
  • "aba" (odd) becomes "#a#b#a#" (still odd in terms of center)
  • "bb" (even) becomes "#b#b#" (now odd, center at the middle '#')

2. Mirror Property:
If we're inside a known palindrome, we can use the mirror position to get information for free.

Imagine we know there's a palindrome centered at position C with right boundary R:

        L           C           R
        |-----------|-----------|  
             i'          i

If position i is within this palindrome (i < R), then its mirror position i' = 2C - i has the same local structure. We can use the palindrome length at i' as a starting point for i, potentially skipping many comparisons.

3. Avoiding Redundant Work:
As we move through the string, we maintain the rightmost boundary R of any palindrome we've found. For each new position:

  • If it's inside R, use the mirror property
  • If it's outside R, start fresh
  • After any expansion, update R if we extended beyond it

This ensures each character is visited at most twice (once for expanding, once for being mirrored), giving us O(n) time.

Step-by-Step Explanation

Let's trace through with s = "babad":

Step 1: Transform the string
Original: "babad"
Transformed: "@#b#a#b#a#d#$"

  • '@' is left sentinel (avoids bounds checking)
  • '$' is right sentinel
  • '#' separates characters

Step 2: Initialize

  • P[i] = radius of palindrome centered at i
  • C = 0 (center), R = 0 (right boundary)

Step 3: Process each position

T:  @ # b # a # b # a # d  #  $
    0 1 2 3 4 5 6 7 8 9 10 11 12

i = 2 ('b'): P[2] = 0, expand: T[1]='#' vs T[3]='#' → same! P[2]=1. T[0]='@' vs T[4]='a' → different. P[2]=1, C=2, R=3.

i = 4 ('a'): i > R (4 > 3), P[4] = 0. Expand: T[3]='#' vs T[5]='#' → same! P[4]=1. T[2]='b' vs T[6]='b' → same! P[4]=2. T[1]='#' vs T[7]='#' → same! P[4]=3. T[0]='@' vs T[8]='a' → different. P[4]=3, C=4, R=7. This is the max! Corresponds to palindrome radius 3 in original.

i = 6 ('b'): i ≤ R (6 ≤ 7), mirror = 2*4-6 = 2. P[6] = min(P[2], R-i) = min(1, 1) = 1. Expand beyond: T[4]='a' vs T[8]='a' → same! P[6]=2. T[3]='#' vs T[9]='#' → same! P[6]=3. T[2]='b' vs T[10]='d' → different. P[6]=3, C=6, R=10. P[6]=3 which ties P[4]. The mirror property gave us a head start!

Step 4: Convert back
Max P value = 3 at position 4. Original length = 3, start = (4 - 3)/2 = 0.
Result: s[0:3] = "bab"

Manacher's Algorithm — Mirror Property Skips Redundant Work — Watch how the algorithm transforms the string, then uses the mirror property within known palindromes to skip comparisons. When position i falls within the rightmost palindrome boundary R, its mirror i' provides a starting radius for free.

Algorithm

  1. Transform the input string:

    • Add '#' between every character
    • Add sentinels '@' at start and '$' at end
    • Example: "abc" → "@#a#b#c#$"

  2. Initialize:

    • Array P of size len(transformed) to store palindrome radii
    • C = 0 (center of rightmost palindrome found)
    • R = 0 (right boundary of rightmost palindrome)

  3. For each position i from 1 to len(transformed)-2:

    • If i < R: Use mirror property to initialize P[i] = min(P[2*C - i], R - i)
    • Else: P[i] = 0
    • Expand: While characters at positions (i - P[i] - 1) and (i + P[i] + 1) match, increment P[i]
    • If i + P[i] > R: Update C = i and R = i + P[i]
    • Track the position with maximum P[i]

  4. Convert back to original string:

    • Original length = P[maxCenter]
    • Original start = (maxCenter - P[maxCenter]) / 2
    • Return substring from original

Code

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        
        // Transform string: "abc" -> "@#a#b#c#$"
        string t = "@";
        for (char c : s) {
            t += "#";
            t += c;
        }
        t += "#$";
        
        int n = t.length();
        vector<int> p(n, 0);
        int center = 0, right = 0;
        int maxLen = 0, maxCenter = 0;
        
        for (int i = 1; i < n - 1; i++) {
            // Use mirror property if i is within the right boundary
            if (i < right) {
                int mirror = 2 * center - i;
                p[i] = min(p[mirror], right - i);
            }
            
            // Attempt to expand palindrome centered at i
            while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
                p[i]++;
            }
            
            // Update center and right boundary
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            
            // Track the longest palindrome
            if (p[i] > maxLen) {
                maxLen = p[i];
                maxCenter = i;
            }
        }
        
        int start = (maxCenter - maxLen) / 2;
        return s.substr(start, maxLen);
    }
};
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        
        # Transform string: "abc" -> "@#a#b#c#$"
        t = "@" + "#" + "#".join(s) + "#$"
        
        n = len(t)
        p = [0] * n
        center = 0
        right = 0
        max_len = 0
        max_center = 0
        
        for i in range(1, n - 1):
            # Use mirror property if i is within the right boundary
            if i < right:
                mirror = 2 * center - i
                p[i] = min(p[mirror], right - i)
            
            # Attempt to expand palindrome centered at i
            while t[i + p[i] + 1] == t[i - p[i] - 1]:
                p[i] += 1
            
            # Update center and right boundary
            if i + p[i] > right:
                center = i
                right = i + p[i]
            
            # Track the longest palindrome
            if p[i] > max_len:
                max_len = p[i]
                max_center = i
        
        start = (max_center - max_len) // 2
        return s[start:start + max_len]
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";
        
        StringBuilder sb = new StringBuilder("@");
        for (char c : s.toCharArray()) {
            sb.append("#");
            sb.append(c);
        }
        sb.append("#$");
        String t = sb.toString();
        
        int n = t.length();
        int[] p = new int[n];
        int center = 0, right = 0;
        int maxLen = 0, maxCenter = 0;
        
        for (int i = 1; i < n - 1; i++) {
            if (i < right) {
                int mirror = 2 * center - i;
                p[i] = Math.min(p[mirror], right - i);
            }
            
            while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) {
                p[i]++;
            }
            
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            
            if (p[i] > maxLen) {
                maxLen = p[i];
                maxCenter = i;
            }
        }
        
        int start = (maxCenter - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }
}

Complexity Analysis

Time Complexity: O(n)

Although there's a while loop inside the for loop, the total number of character comparisons across all iterations is bounded by O(n). Here's why:

  • The right boundary R only moves to the right and never decreases
  • Each character can trigger at most one expansion (when R moves past it)
  • Once R has moved past a position, no further expansions start from positions before R that would re-examine that character

This amortized analysis shows that each character is compared at most twice, giving us O(n) total time.

Space Complexity: O(n)

We use:

  • The transformed string T of size 2n + 3 = O(n)
  • The array P of size 2n + 3 = O(n)

Total space is O(n).

Note: This is the theoretically optimal solution. We cannot do better than O(n) time because we must read every character at least once. The O(n) space is also necessary for the algorithm's bookkeeping, though there exist constant-space O(n²) solutions if space is more critical than time.