Leetcode - Longest Palindromic Substring

Question

Given a string s, return the longest palindromic substring in s.

Idea

• Use a sliding window approach
• Two cases: odd substrings and even substring
• Treat current index like the center of the palindrome or the 2 centres of the palindrome in even cases
• Do 2 passes:
  • Even: set l, r to i-1 and i+2 to extend out from i Extend out left and right evenly making sure they are the same letter
  • Odd: set l, r to i, i+1 and extend out

The canonical solution here is an O(n^2) solution, where I spent a lot of time trying to find a linear solution. Sometimes you just can’t. Always remember that for a subproblem, you can run the subproblem across a solution space (across every index in an array/matrix).

Solution