Longest Palindromic Substring

The problem

A palindrome reads the same forward and backward. Return the longest palindrome that appears inside s as a substring, which means a run of characters that sit next to each other in s. If several palindromes share the greatest length, return the one that starts first. A single character is a palindrome, so there is always an answer.

What to write

function solve(s: string): string

Input
s = "babad"

Output
"bab"

Input
s = "cbbd"

Output
"bb"

Constraints

1 ≤ s.length ≤ 1000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   s has at most 1000 characters, so it has up to 500,500 substrings. Checking each of them letter by letter reads the same letters again and again. A single character is always a palindrome, so the answer always has at least one character.

2. Hint 2: Ask a smaller question

   Suppose you already know that "cec" is a palindrome inside "racecar". What is the least you have to compare to find out whether "aceca" is one too? And after that, "racecar"?

3. Hint 3: Name the pattern

   A palindrome stays a palindrome when you remove its first and last letters. So every palindrome can be found by starting at its middle and growing outward while the two end letters match. The middle is one letter, or two letters side by side. This is called expand around a center. Read the lesson on expand around a center.

4. Hint 4: State the invariant

   While you grow from one center, the piece between the two ends is always a palindrome, because every pair of end letters matched so far. The first pair that differs, or the edge of s, ends that center: no wider piece around it can be a palindrome.

5. Hint 5: Sketch the pseudocode

   start = 0, length = 0. For each position i and offset 0, then 1: left = i, right = i + offset. While both are inside s and their letters match: if right - left + 1 > length, store left and that length; then step left down and right up. Return that piece of s.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Expand around each odd and even center, tracking the longest palindrome found.

The slow way

Check every substring: read it from both ends inward and keep the longest one that is a palindrome. It is correct, but there are about n × n / 2 substrings, and one check can take about n / 2 comparisons. For 1000 equal letters that comes to 83,458,250 comparisons.

The insight

Remove the first and last letters of a palindrome and what is left is a palindrome around the same middle. So you can work the other way: start at a middle, called a center, and grow outward one letter on each side. Each round costs one comparison, and the first mismatch tells you that no wider piece around this center can be a palindrome.

Step by step

1. Keep the start and the length of the longest palindrome so far. Two numbers are enough to cut the answer out of s at the end. The length starts at 0, so the first single letter that is checked becomes the first record.
2. Try each center in turn: one letter, then that letter and the next. A palindrome of odd length, such as "aba", has one middle letter. A palindrome of even length, such as "abba", has two. Trying both kinds at every position covers every palindrome in s.
3. While both ends are inside s and hold the same letter. Matching ends around a palindrome make a longer palindrome. A mismatch, or an end that has left s, means no wider piece around this center can be one, so this center is finished.
4. Record this palindrome if it is longer than the longest so far. Only a strictly longer palindrome replaces the record. An equally long one found later is ignored, which is how the palindrome that starts first wins a tie.
5. Move both ends one letter outward. The next candidate around the same center is one letter wider on each side. Only its two new end letters need comparing, because everything between them is already known to match.
6. Cut the longest palindrome out of s. The record holds where the longest palindrome starts and how long it is, so the answer is the piece of s from that start for that many letters.

The same numbered steps are the comments in each solution.

function solve(s) {
  // 1. Keep the start and the length of the longest palindrome so far
  let start = 0;
  let length = 0;
  // 2. Try each center in turn: one letter, then that letter and the next
  for (let i = 0; i < s.length; i++)
    for (const offset of [0, 1]) {
      let left = i;
      let right = i + offset;
      // 3. While both ends are inside s and hold the same letter
      while (left >= 0 && right < s.length && s[left] === s[right]) {
        // 4. Record this palindrome if it is longer than the longest so far
        if (right - left + 1 > length) {
          start = left;
          length = right - left + 1;
        }
        // 5. Move both ends one letter outward
        left--;
        right++;
      }
    }
  // 6. Cut the longest palindrome out of s
  return s.slice(start, start + length);
}

function solve(s: string): string {
  // 1. Keep the start and the length of the longest palindrome so far
  let start = 0;
  let length = 0;
  // 2. Try each center in turn: one letter, then that letter and the next
  for (let i = 0; i < s.length; i++)
    for (const offset of [0, 1]) {
      let left = i;
      let right = i + offset;
      // 3. While both ends are inside s and hold the same letter
      while (left >= 0 && right < s.length && s[left] === s[right]) {
        // 4. Record this palindrome if it is longer than the longest so far
        if (right - left + 1 > length) {
          start = left;
          length = right - left + 1;
        }
        // 5. Move both ends one letter outward
        left--;
        right++;
      }
    }
  // 6. Cut the longest palindrome out of s
  return s.slice(start, start + length);
}

def solve(s):
    # 1. Keep the start and the length of the longest palindrome so far
    start = 0
    length = 0
    # 2. Try each center in turn: one letter, then that letter and the next
    for i in range(len(s)):
        for offset in (0, 1):
            left = i
            right = i + offset
            # 3. While both ends are inside s and hold the same letter
            while left >= 0 and right < len(s) and s[left] == s[right]:
                # 4. Record this palindrome if it is longer than the longest so far
                if right - left + 1 > length:
                    start = left
                    length = right - left + 1
                # 5. Move both ends one letter outward
                left -= 1
                right += 1
    # 6. Cut the longest palindrome out of s
    return s[start : start + length]

Example 1, traced

Input
s = "babad"

Output
"bab"

Why it works

Every palindrome has a center, and the method tries every center. From a center, the method finds each palindrome around that center, shortest first, and stops only at a mismatch or an edge, after which no wider piece around the same center can be a palindrome. So every palindrome in s is seen once, and the record keeps the first of the longest.

Time and space

Time O(n²), extra space O(1). There are 2n centers for n letters. From one center the ends can move outward at most about n / 2 times before one of them leaves s, so the time is O(n²). Only a few numbers are kept besides the answer, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Try the two-letter centers as well. A palindrome of even length has no single middle letter, so with one-letter centers only, example 2 returns "c" instead of "bb".
• Replace the record only when the new palindrome is longer, not when it is equally long. Otherwise a later palindrome pushes out the first one, and example 1 returns "aba" instead of "bab".
• In Python, check that the left end is at least 0 before you read the letter there. Position -1 means the last letter, so without the check the loop keeps going by mistake: "ac" returns "c" instead of "a".

Pattern

Expand around a center. Builds on Valid Palindrome.

Keep going