Level Order

Solution	Time	Space
Brute force	O(n³)	O(1)
Dynamic programming	O(n²)	O(n²)
Central expansion	O(n²)	O(1)
Manacher's algorithm	O(n)	O(n)

Solution 1: Brute force

Use two loops to iterate over all possible substrings:

The outer loop provides the start index of a substring
The inner loop provides the end index of a substring

For each substring, check if it's a palindrome.

If it's a palindrome
- See if it's longer than the longest palindrome we've seen so far
- If it is, save the start and end indices of the substring
If it isn't, move on to the next substring

Afterwards, we'll have the start and end indices of the longest palindrome.

def longest_palindromic_substring(s)
  n = s.length
  i_start = i_end = 0
  (0 .. n-2).each do |i|
    (i+1 .. n-1).each do |j|
      substr = s[i .. j]
      if substr == substr.reverse && j - i > i_end - i_start
        i_start, i_end = i, j
      end
    end
  end
  s[i_start .. i_end]
end

Time	O(n³)	Each of O(n²) substrings takes O(n) time to check
Space	O(1)	The start/end indices of the longest palindrome

Solution 2: Dynamic programming

This improves the runtime of the brute force solution by checking whether a substring is a palindrome in O(1) time instead of O(n) time.

It saves time at the expense of space by storing whether a substring is a palindrome in a 2D array, and referencing these values for each longer substring.

Let each value of is_pal[i][j] be

true - when a substring s[i .. j] is a palindrome
false - otherwise

We can check if a substring s[i .. j] is a palindrome in O(1) time:

it's a palindrome if s[i] == s[j] and is_pal[i+1][j-1] is true
otherwise it's not a palindrome

def longest_palindromic_substring(s)
  n = s.length
  return s if n <= 1
  is_pal = Array.new(n) { Array.new(n) }
  i_start = i_end = 0
  (n - 1).downto(0).each do |i|
    i.upto(n - 1).each do |j|
      if j - i < 3
        is_pal[i][j] = s[i] == s[j]
      else
        is_pal[i][j] = s[i] == s[j] && is_pal[i + 1][j - 1]
      end
      if is_pal[i][j] && j - i > i_end - i_start
        i_start, i_end = i, j
      end
    end
  end
  s[i_start .. i_end]
end

Time	O(n²)	Each of O(n²) substrings takes O(1) time to check
Space	O(n²)	2D array of booleans for O(n²) substrings

Solution 3: Central expansion

This improves on the previous two solutions by iterating over all possible centers of palindromes (2n - 1) ~ O(n) instead of iterating over all possible substrings.

A center can be represented by a pair of string indices [i, j]

The center of a palindrome can begin either

on a character for odd-length palindromes - [i, i]
between two characters for even-length palindromes - [i, i + 1]

For each center [i, j], check if the first and last letter match.

If the letters match
- expand the edges outwards to look for a longer palindrome
- store the start/end indices if it's the longest palindrome seen so far
Otherwise move on to the next center

Afterwards, we'll have the start and end indices of the longest palindrome.

def longest_palindromic_substring(s)
  n = s.length
  return s if n <= 1
  i_start = i_end = 0
  (0 .. (2 * n - 1)).each do |i_center|
    i = j = i_center / 2
    j += 1 if i_center % 2 == 1
    while i >= 0 and i < n and j >= 0 and j < n
      break if s[i] != s[j]
      i -= 1
      j += 1
    end
    i += 1
    j -= 1
    if j - i > i_end - i_start
      i_start, i_end = i, j
    end
  end
  s[i_start .. i_end]
end

Time	O(n²)	Each of 2n - 1 centers takes O(n) time to check
Space	O(1)	The start/end indices of the longest palindrome

Solution 4: Manacher's algorithm

This algorithm combines the ideas explored in solutions 2 and 3:

Storing palindrome lengths after finding a palindrome
Central expansion for efficient iteration over palindromes

By using the fact that the left and right sides of a palindrome are mirror images of each other, it avoids re-checking palindromes that have already been found.

If a shorter palindrome is located within the left of the center of a longer palindrome, this shorter palindrome is guaranteed to exist on the right side of the longer palindrome as well. When reaching the center of the shorter palindrome on the right side, the central expansion can begin at the known ends of the palindrome rather from the center.

def longest_palindromic_substring(s)
  t = s.split("").map {|c| "##{c}" }.join + "#"
  t = "^#{t}$"
  p_lengths = Array.new(t.length, 0)
  center = right = 0
  (1 .. t.length-1).each do |i|
    mirror = 2*center - i
    if i < right
      p_lengths[i] = [right - i, p_lengths[mirror]].min
    end
    while t[i - (1+p_lengths[i])] == t[i + (1+p_lengths[i])]
      p_lengths[i] += 1
    end
    if p_lengths[i] + i > right
      center = i
      right = p_lengths[i] + i
    end
  end
  max_length = p_lengths.max
  center = p_lengths.index(max_length)/2 - 1
  p_start = center - max_length/2
  if max_length % 2 == 0
    p_start += 1
  end
  p_end = center + max_length/2
  s[p_start .. p_end]
end

Time	O(n)	Iterating over 2n centers
Space	O(n)	2n space for expanded string with boundary characters

Longest palindromic substring

Solution 1: Brute force

Solution 2: Dynamic programming

Solution 3: Central expansion

Solution 4: Manacher's algorithm

Resources