Blind 75 Visualized

#53 · 1D DP

Longest Palindromic Substring

Given a string s, return its longest palindromic substring (a contiguous part that reads the same forwards and backwards).

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Substring table dp[i][j]

dp[i][j] is true when s[i..j] is a palindrome. It follows from the two end letters and the inner substring: dp[i][j] = (s[i] = s[j]) and dp[i+1][j−1]. Longer substrings are decided from shorter ones.

Memory layout

An n × n boolean grid, of which only the upper triangle is used.

OperationCost
timeO(n²)
spaceO(n²)

Centre expansion

Every palindrome is symmetric about its centre, so grow outwards from each of the 2n − 1 centres while the two outer letters match. No table is needed.

Memory layout

A few integers.

OperationCost
time / spaceO(n²) / O(1)

Manacher's radius array

Insert separators so odd and even palindromes are alike, store a radius per position, and reuse the radius of the mirror position inside the current right-most palindrome. The right edge only moves forward, which makes it linear.

Memory layout

A transformed string of length 2n + 3 and an integer array of the same length.

OperationCost
time / spaceO(n) / O(n)

Why it fits

  • A palindrome that is longer than another contains a smaller palindrome in its middle. That nested structure is why a table of shorter substrings (or a growing window around a centre) works.
  • Centres are the natural unit: a palindrome is determined by its centre and radius, and there are only 2n − 1 centres.
  • Manacher's algorithm exploits symmetry inside a known big palindrome: a position inside it behaves like its mirror, so its answer does not need to be recomputed.

Why alternatives degrade

Reverse the string and take the longest common substring:
It also matches a substring with a reversed copy elsewhere in the string, which is not a palindrome (for example "abacdfgdcaba").
Sort or hash letters:
A palindrome depends on order, and anagram-style tools discard it.
Greedy outward from the middle of the string:
The longest palindrome can be anywhere, so one centre is not enough.

Four approaches, from naive to production

1 · beginner

Test every substring

time O(n³)space O(1)

Enumerate every substring s[i..j]; for those longer than the best so far, compare letters from both ends inwards to test the palindrome property, and keep the longest.

string longestPalindrome(string s) {
    auto isPal = [&](int l, int r) -> bool {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    };
    string best = "";
    for (int i = 0; i < (int)s.size(); i++) {
        for (int j = i; j < (int)s.size(); j++) {
            if (j - i + 1 > (int)best.size() && isPal(i, j)) best = s.substr(i, j - i + 1);
        }
    }
    return best;
}

Flaws & bottlenecks

  • n² substrings, each tested in O(n): cubic.
  • Palindrome tests repeat work: "abcba" re-checks the inner "bcb" that was checked for a shorter substring.
  • Slicing a substring for every improvement allocates.

Interviewer cross-questions

Why skip substrings that are not longer than the best?

Say: They cannot improve the answer, and the length comparison is O(1) while the palindrome test is O(n).

Which work is repeated?

Say: To test s[i..j] you compare s[i] with s[j] and then test s[i+1..j−1] again from scratch. That inner substring was already tested (or can be) as a shorter candidate.

How do you avoid it?

Say: Either remember the answer for each inner substring (DP table) or grow palindromes outward from their centres so no substring is tested twice.

2 · intermediate

DP table of substrings

time O(n²)space O(n²)

dp[i][j] is true when s[i..j] is a palindrome: its end letters match and the inside is a palindrome (or has at most two letters). Fill the table by increasing length and remember the longest true entry.

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, bestLen = 1;
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && (len <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (len > bestLen) {
                    start = i;
                    bestLen = len;
                }
            }
        }
    }
    return s.substr(start, bestLen);
}

Flaws & bottlenecks

  • O(n²) memory, which is large for long strings.
  • Every cell is computed even though most substrings are not palindromes.
  • The loop order (by length) is easy to get wrong: iterating i then j without care reads cells that are not computed yet.

Interviewer cross-questions

Why iterate by length?

Say: dp[i][j] reads dp[i+1][j−1], a shorter substring. Processing lengths in increasing order guarantees it is ready.

Why len <= 2 instead of reading dp?

Say: For lengths 1 and 2 the inner substring is empty or out of range, so only the end letters matter (a single letter is a palindrome; two letters are one if they are equal).

Can you reduce the memory?

Say: Each row depends only on the row below, so a rolling array works for a yes/no answer, but you then lose the table needed to reconstruct. Centre expansion uses O(1) memory.

3 · advanced

Expand around each centre

time O(n²)space O(1)

There are 2n − 1 possible centres (each letter, and each gap between letters). Expand outwards from each while the two outer letters are equal, and remember the longest window.

string longestPalindrome(string s) {
    int start = 0, end = 0;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < (int)s.size() && s[l] == s[r]) {
            if (r - l > end - start) {
                start = l;
                end = r;
            }
            l--;
            r++;
        }
    };
    for (int c = 0; c < (int)s.size(); c++) {
        expand(c, c);
        expand(c, c + 1);
    }
    return s.substr(start, end - start + 1);
}

Flaws & bottlenecks

  • A string like "aaaa…a" makes every expansion run to the edge: genuinely quadratic.
  • Easy to forget the even-length centres (the gap between two letters).
  • Slices the answer only at the end, but updates start and end repeatedly inside the loop.

Interviewer cross-questions

Why 2n − 1 centres?

Say: An odd palindrome is centred on a letter (n choices) and an even one on a gap between two letters (n − 1 choices).

Is it really O(n²)?

Say: The worst case is a string of equal letters where every expansion goes to the boundary. For typical text the expansions stop very early and it is much faster.

Can you do better than quadratic?

Say: Yes: Manacher's algorithm finds the longest palindrome in O(n) by reusing the radii inside a known large palindrome.

4 · expert

Manacher's algorithm

time O(n)space O(n)

Put a separator between all letters so every palindrome has odd length, then compute a radius for each position. Inside the right-most palindrome found so far, start a position's radius from its mirror's radius; only expand beyond the known edge. Then convert the best radius back.

string longestPalindrome(string s) {
    string t = "^#"; for (char ch : s) { t += ch; t += '#'; } t += '$';
    vector<int> p(t.size(), 0);
    int center = 0, right = 0;
    for (int i = 1; i < (int)t.size() - 1; i++) {
        if (i < right) p[i] = min(right - i, p[2 * center - i]);
        while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    int bestLen = 0, bestCenter = 0;
    for (int i = 1; i < (int)t.size() - 1; i++) {
        if (p[i] > bestLen) {
            bestLen = p[i];
            bestCenter = i;
        }
    }
    int start = (bestCenter - bestLen) / 2;
    return s.substr(start, bestLen);
}

Flaws & bottlenecks

  • Subtle: the mirror formula and the guards are easy to get wrong.
  • Uses a transformed copy of the string and a radius array, so more memory than centre expansion.
  • For short strings (typical interviews) the gain is invisible and the code is harder to defend.

Interviewer cross-questions

Why is it linear?

Say: The right edge of the right-most palindrome never moves left. Each successful letter comparison pushes it right by at least one step, so the total number of comparisons is at most the length of the transformed string.

Why add separators?

Say: Without them odd and even palindromes need different centres. With "#" between letters every palindrome (in the new string) is centred on a position and has odd length, so one loop handles both.

What are the ^ and $ guards for?

Say: They are two different characters that match nothing, so the while loop stops at both ends without separate bounds checks.

Synchronized code walkthrough

Showing: Test every substring — shares the player above; click any step to jump.

string longestPalindrome(string s) {
    auto isPal = [&](int l, int r) -> bool {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    };
    string best = "";
    for (int i = 0; i < (int)s.size(); i++) {
        for (int j = i; j < (int)s.size(); j++) {
            if (j - i + 1 > (int)best.size() && isPal(i, j)) best = s.substr(i, j - i + 1);
        }
    }
    return best;
}