101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Expand Around Center Approach - Complex approach
  2. Dynamic Programming Approach - Complex approach
  3. Manacher's Algorithm - Complex approach

Approach 1: Expand Around Center Approach

The key insight for solving this problem efficiently is to use the "expand around center" approach. Since a palindrome mirrors around its center, we can check each possible center and expand outward to find the longest palindrome.

There are two types of palindromes to consider:

  1. Odd-length palindromes, which have a single character at the center (e.g., "racecar" has 'e' at the center).
  2. Even-length palindromes, which have two identical characters at the center (e.g., "abba" has 'b' and 'b' at the center).

For each position in the string, we check both types of palindromes by expanding around that position.

Algorithm:

  1. Iterate through each position i in the string:
  2. a. Expand around center i for odd-length palindromes (single character at the center).
  3. b. Expand around centers i and i+1 for even-length palindromes (two characters at the center).
  4. c. Keep track of the longest palindrome found so far.
  5. Return the longest palindromic substring.

Time Complexity:

O(n²)

Where n is the length of the string. For each of the n positions, we might need to expand up to n/2 steps outward in the worst case.

Space Complexity:

O(1)

We only need a constant amount of extra space to store the indices of the longest palindrome found so far.

Approach 2: Dynamic Programming Approach

Another approach is to use dynamic programming. We'll define a 2D DP table where dp[i][j] is true if the substring s[i...j] is a palindrome, and false otherwise.

The key recurrence relation is:

dp[i][j] = true if s[i] == s[j] and (j - i < 2 or dp[i+1][j-1] is true)

This means that a substring is a palindrome if its first and last characters are the same, and the substring between them is also a palindrome (or is empty).

Algorithm:

  1. Create a 2D DP table of size n×n, where n is the length of the string.
  2. Initialize all values in the DP table to false.
  3. Set dp[i][i] = true for all i, as single characters are palindromes.
  4. Set dp[i][i+1] = true if s[i] == s[i+1], as two identical adjacent characters form a palindrome.
  5. Fill the DP table for longer substrings:
  6. a. For each length len from 3 to n:
  7. i. For each starting position i from 0 to n-len:
  8. 1. Calculate the ending position j = i+len-1.
  9. 2. Set dp[i][j] = true if s[i] == s[j] and dp[i+1][j-1] is true.
  10. Keep track of the longest palindromic substring found during this process.
  11. Return the longest palindromic substring.

Time Complexity:

O(n²)

Where n is the length of the string. We need to fill a 2D DP table of size n×n, and each cell takes constant time to compute.

Space Complexity:

O(n²)

We need a 2D DP table of size n×n to store the intermediate results.

Approach 3: Manacher's Algorithm

Manacher's algorithm is a highly optimized approach that can solve the longest palindromic substring problem in linear time. The key insight is to reuse the information from previously computed palindromes to avoid redundant calculations.

The algorithm works by transforming the original string to handle both odd and even-length palindromes uniformly, and then using a clever technique to expand palindromes only when necessary.

Algorithm:

  1. Transform the original string by inserting a special character (e.g., &apos;#&apos;) between each character and at the beginning and end.
  2. Initialize an array P where P[i] represents the radius of the palindrome centered at position i in the transformed string.
  3. Maintain variables for the center (C) and right boundary (R) of the rightmost palindrome found so far.
  4. Iterate through each position i in the transformed string:
  5. a. If i < R, initialize P[i] = min(R - i, P[2*C - i]) to take advantage of the mirror property.
  6. b. Expand around center i as far as possible.
  7. c. If i + P[i] > R, update C and R.
  8. Find the maximum value in P and its corresponding center.
  9. Convert the result back to the original string format and return the longest palindromic substring.

Time Complexity:

O(n)

Where n is the length of the string. Each character is visited at most twice: once when it becomes part of the rightmost palindrome, and once when we expand around it as a center.

Space Complexity:

O(n)

We need an array of size 2n+1 to store the radii of palindromes in the transformed string.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function longestPalindrome(s):
    if s is empty or has length 1:
        return s
 
    start = 0
    maxLength = 1
 
    function expandAroundCenter(left, right):
        while left >= 0 and right < length of s and s[left] == s[right]:
            left--
            right++
 
        // Return the length of the palindrome
        return right - left - 1
 
    for i from 0 to length of s - 1:
        // Expand for odd-length palindromes
        len1 = expandAroundCenter(i, i)
 
        // Expand for even-length palindromes
        len2 = expandAroundCenter(i, i + 1)
 
        // Find the maximum length
        len = max(len1, len2)
 
        // Update the longest palindrome if needed
        if len > maxLength:
            maxLength = len
            start = i - (len - 1) / 2
 
    return substring of s from start to start + maxLength
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone