Longest Palindromic Substring

The problem

Given a string text, return its longest substring that is a palindrome: it reads the same forwards and backwards. A substring is a run of letters next to each other. If several are equally long, return any one.

Example 1

Input: text = "cabbad"

Output: "abba"

“abba” reads the same both ways. “cabbac” would too, but the string ends in “d”, not “c”.

text

c0a1b2b3a4d5

Example 2

Input: text = "xyz"

Output: "x"

No two letters match, so any single letter is the longest palindrome. “y” or “z” is also accepted.

Example 3

Input: text = "kayak"

Output: "kayak"

The whole string is a palindrome.

Constraints

• 1 ≤ text.length ≤ 1000 (call it n)
• Only English letters and digits.

Clarifying questions

Substring or subsequence?

Substring: the letters must be next to each other in text.

Is a single letter a palindrome?

Yes. So the answer always has at least one letter.

If there is a tie, which one?

Any of them is accepted.

Does case matter?

Yes. "A" and "a" are different letters.

Spot the pattern

To check one palindrome, you compare letters in pairs from the two ends inward, or from the middle outward: two pointers moving in opposite directions. The trick is to pick the direction that lets one pass check many palindromes at once. Going outward from a middle checks every palindrome with that middle, from shortest to longest, in a single walk.

Solutions

Check every substringO(n³)Expand around centersO(n²)

Show all

There is no middle approach worth its own tab. A table that records which substrings are palindromes also takes O(n²) time, but needs O(n²) memory, so it is worse than expanding. Manacher's algorithm reaches O(n), but it is rarely expected in an interview.

Check every substring O(n³)

The idea

Try every pair of start i and end j. For each substring, check it with two pointers: compare the first and last letter, then the second and second to last, and so on, stopping at the first mismatch. Keep the longest one that passes.

Why it is correct: the answer is one of the substrings, and every substring is checked.

Walkthrough

text

c0a1b2b3a4d5

longest

-

1. for i in 0 .. len(text) - 1:
2. for j in i .. len(text) - 1:
3. if text[i..j] reads the same both ways: # two pointers
4. keep it if it is the longest so far
5. return the longest

Try every substring: every start i and every end j. Check each with two pointers from the outside in, and keep the longest palindrome.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: check every substring with two pointers and keep the longest
    // palindrome. There are about n²/2 substrings, and each check reads up to n letters.
    public String longestPalindrome(String text) {
        int start = 0, length = 0;
        for (int i = 0; i < text.length(); i++) {
            for (int j = i; j < text.length(); j++) {
                if (isPalindrome(text, i, j) && j - i + 1 > length) {
                    start = i;
                    length = j - i + 1;
                }
            }
        }
        return text.substring(start, start + length);
    }

    private boolean isPalindrome(String text, int left, int right) {
        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

Big O

Time O(n³)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The inner for runs once per substring, and each run starts a check. Inside the check, the while loop compares one pair of letters per run. Both are fixed jobs, so each substring and each pair compared counts as 1 step.

   1. for i in 0 .. len(text) - 1:
   2. for j in i .. len(text) - 1:
   3. if text[i..j] reads the same both ways: # two pointers
   4. keep it if it is the longest so far
   5. return the longest

2. 2 Count the runs on Example 1

   The table has one column per start. Start 0 has 6 substrings, start 5 has only 1. Most checks stop at the first pair, because the outer letters differ.

   21 substrings + 16 pairs = 37 steps.

   start i	0	1	2	3	4	5
   substrings	6	5	4	3	2	1
   pairs compared	5	5	3	2	1	0

   total

   21 substrings + 16 pairs = 37 steps

3. 3 Write the count for any n

   There are n + (n − 1) + … + 1 = n × (n + 1) / 2 substrings. A check compares at most n / 2 pairs:

   n × (n + 1) / 2 × (1 + n / 2) steps

   Check it with Example 1: 21 × 4 = 84 at most. The real run used 37. The worst case is a string of one letter repeated, like “aaaaaa”, where every check runs to the middle.

4. 4 Keep only the part that grows fastest

   Multiply it out and the biggest term is n³ / 4. Drop the 1/4 and the smaller terms. What is left is n³. For n = 1000 that is about 250 million steps.

   So the time is O(n³).

5. S Space: count the extra memory the same way

   The code keeps only the best start and length, and two pointers. So the space is O(1), not counting the answer string.

   start, lengthleft, right

Expand around centers O(n²)

The idea

The brute force checks “bb”, then separately “abba”, comparing the inner “bb” again. But “abba” is just “bb” with one more matching letter on each side. So grow palindromes from the inside out.

Every palindrome has a middle. In an odd-length palindrome, like “kayak”, the middle is a letter. In an even-length one, like “abba”, it is the gap between two letters. A string of n letters has n letter middles and n − 1 gap middles.

For each middle, put left and right on its two sides and move them outward while text[left] == text[right]. When they stop, the palindrome is the letters strictly between them. Keep the longest.

Why it is correct: the longest palindrome has some middle, and expanding from that middle keeps going for as long as the letters match, so it finds the whole palindrome.

Walkthrough

text

c0a1b2b3a4d5

longest

-

1. for center in 0 .. len(text) - 1:
2. for (left, right) in (center, center), (center, center + 1): # letter or gap
3. while left >= 0 and right < len(text) and text[left] == text[right]: left -= 1; right += 1
4. length = right - left - 1
5. keep text[left + 1 .. right - 1] if it is the longest so far
6. return the longest

A palindrome mirrors around its middle. The middle is a letter, like the "y" of "kayak", or a gap between two letters, like the middle of "abba". Try each middle and grow outward while the two ends match.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private int start, length;

    // Expand around each center: every palindrome mirrors around its middle, so
    // grow outward from all 2n - 1 middles. Each center costs at most n/2 steps: O(n²) time, O(1) space.
    public String longestPalindrome(String text) {
        for (int center = 0; center < text.length(); center++) {
            // Odd lengths have a middle letter; even lengths have a middle gap.
            expand(text, center, center);
            expand(text, center, center + 1);
        }
        return text.substring(start, start + length);
    }

    private void expand(String text, int left, int right) {
        while (left >= 0 && right < text.length() && text.charAt(left) == text.charAt(right)) {
            left--;
            right++;
        }
        // The loop stopped one step too far on each side.
        if (right - left - 1 > length) {
            start = left + 1;
            length = right - left - 1;
        }
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The outer loop tries 2 middles per letter. For each, the while loop compares one pair of letters per run. Both are fixed jobs, so each middle and each pair compared counts as 1 step.

   1. for center in 0 .. len(text) - 1:
   2. for (left, right) in (center, center), (center, center + 1): # letter or gap
   3. while left >= 0 and right < len(text) and text[left] == text[right]: left -= 1; right += 1
   4. length = right - left - 1
   5. keep text[left + 1 .. right - 1] if it is the longest so far
   6. return the longest

2. 2 Count the runs on Example 1

   The table has one column per letter, with a row for its letter middle and its gap middle. The gap between 2 and 3 does the most: “bb”, then “abba”, then the failed “cabbad”.

   12 middles + 17 pairs = 29 steps.

   c	0	1	2	3	4	5
   letter middle	1	2	2	2	2	1
   gap middle	1	1	3	1	1	0

   total

   12 middles + 17 pairs = 29 steps

3. 3 Write the count for any n

   There are 2 × n middles in the loop. From a middle, the pointers can move at most n / 2 places before one falls off an end, so at most n / 2 + 1 pairs are compared:

   2 × n × (1 + n / 2 + 1) = n² + 4 × n steps

   Check it with Example 1: 36 + 24 = 60 at most. The real run used 29.

4. 4 Keep only the part that grows fastest

   Drop the 4 × n. It grows slower than n². What is left is n². For n = 1000 that is about a million steps, not 250 million.

   So the time is O(n²).

5. S Space: count the extra memory the same way

   Only the best start and length, and two pointers. So the space is O(1).

   start, lengthleft, right

Common mistake

Only trying letter middles

Expanding only from letters finds odd-length palindromes. “abba” has no middle letter, so it would be missed, and Example 1 would return a single letter. Try each gap as a middle too.

Tested at the limits

2,000 random strings of 1 to 14 characters from two or three letters (sometimes with a capital or a digit), so palindromes and ties are everywhere. Any longest palindrome is right, so each answer was checked to be a palindrome in the text, and check every substring and expand around centers always found the same longest length.

Largest inputs	Result
1,000 copies of one letter (the most allowed), so every center grows all the way to an edge. Expand around centers.	0.04 s, and under 0.001 MB of extra memory: just a few indexes.
150 copies of one letter. Check every substring.	0.02 s. At 1,000 letters it would do about 300 times more work, because the cost grows with n³.