Longest Palindromic Substring: symmetry as the engine, not a trick

Most string problems give you a property and ask you to find the substring satisfying it. This one is different in a subtle way: palindromes have internal structure. Every palindrome is its own reflection around a center. That structural fact is what makes O(n^3) avoidable — not a clever data structure, just the observation that you can grow outward instead of scanning inward.

The problem

Given a string s, find and return the longest substring that reads the same forwards and backwards; if multiple substrings share the maximum length, any one of them is acceptable. Full statement: LeetCode 5.

Constraints:
- 1 <= s.length <= 1000
- s consist of only digits and English letters.

What n <= 1000 actually forces

Read the constraint carefully. n = 1000 allows O(n^2) comfortably — a million operations, runs in milliseconds. It makes O(n^3) borderline — a billion operations in the worst case, which will time out on LeetCode. And it makes Manacher's algorithm (O(n)) unnecessary: you do not need the exotic linear solution here.

The constraint is telling you precisely one thing: you need O(n^2), and you have two ways to get there — expand-from-center or DP. Brute force at O(n^3) teaches you what the right structure looks like by showing you what the wrong one costs.

The character set (digits and English letters) does not constrain the algorithm in any meaningful way. No hash trick, no alphabet counting. Just comparison.

Approach 1: brute force

Check every possible substring. For each pair (i, j), determine whether s[i..j] is a palindrome, track the longest one.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def is_palindrome(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
 
        n = len(s)
        longest = ""
 
        for i in range(n):
            for j in range(i, n):
                if is_palindrome(i, j) and j - i + 1 > len(longest):
                    longest = s[i:j + 1]
 
        return longest

public class Solution {
    public string LongestPalindrome(string s) {
        bool IsPalindrome(int left, int right) {
            while (left < right) {
                if (s[left] != s[right]) return false;
                left++;
                right--;
            }
            return true;
        }
 
        int n = s.Length;
        string longest = "";
 
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (IsPalindrome(i, j) && j - i + 1 > longest.Length) {
                    longest = s.Substring(i, j - i + 1);
                }
            }
        }
 
        return longest;
    }
}

Time: O(n^3). There are O(n^2) pairs (i, j), and is_palindrome scans up to O(n) characters each time. Space: O(1) excluding the output string.

The waste here is obvious once you think about it. When you check whether s[0..4] is a palindrome, you are re-examining the same characters you already inspected for s[1..3], s[2..2], and so on. Every palindrome check repeats work that previous checks already did. That is the redundancy DP eliminates and that center-expansion sidesteps entirely.

Approach 2: expand around centers

Every palindrome has a center. Odd-length palindromes ("aba", "racecar") have a single character at the center. Even-length palindromes ("abba", "bb") have a gap between two characters as the center. There are exactly 2n - 1 possible centers in a string of length n: n single-character centers and n - 1 gap centers.

The insight: instead of asking "is this substring a palindrome?", ask "how far can I expand from this center?" Starting at a center and expanding outward, each successful expansion adds two matching characters to a confirmed palindrome. You stop the moment the outer characters do not match. The total work across all 2n - 1 centers is O(n^2) — each character participates as an outer boundary at most once per center — but critically the inner work does not repeat.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # left and right overshot by one in each direction
            return s[left + 1:right]
 
        if not s:
            return ""
 
        longest = ""
 
        for i in range(len(s)):
            # odd-length: center is character i
            odd = expand(i, i)
            # even-length: center is the gap between i and i+1
            even = expand(i, i + 1)
 
            if len(odd) > len(longest):
                longest = odd
            if len(even) > len(longest):
                longest = even
 
        return longest

public class Solution {
    public string LongestPalindrome(string s) {
        string Expand(int left, int right) {
            while (left >= 0 && right < s.Length && s[left] == s[right]) {
                left--;
                right++;
            }
            // left and right overshot; actual palindrome is [left+1, right-1]
            return s.Substring(left + 1, right - left - 1);
        }
 
        if (string.IsNullOrEmpty(s)) return "";
 
        string longest = "";
 
        for (int i = 0; i < s.Length; i++) {
            string odd = Expand(i, i);
            string even = Expand(i, i + 1);
 
            if (odd.Length > longest.Length) longest = odd;
            if (even.Length > longest.Length) longest = even;
        }
 
        return longest;
    }
}

Time: O(n^2). Space: O(1) — only a handful of integer indices and a reference to the best substring found so far, no auxiliary structure.

Hand trace: s = "babad"

Walk each center:

i=0, center 'b':

• Odd expand: left=0, right=0. Check s[-1]? Out of bounds immediately. Result: "b" (length 1).
• Even expand: left=0, right=1. s[0]='b', s[1]='a'. Mismatch. Result: "".

i=1, center 'a':

• Odd expand: left=1, right=1 -> s[0]='b', s[2]='b', match -> left=0, right=2. Next: left=-1, out of bounds. Result: s[1:2]... wait, let me retrace carefully.
  • Start: left=1, right=1.
  • Iteration 1: s[1]='a' == s[1]='a' -> decrement/increment -> left=0, right=2.
  • Iteration 2: s[0]='b' == s[2]='b' -> left=-1, right=3.
  • Iteration 3: left=-1, exit loop. Return s[-1+1:3] = s[0:3] = "bab". Length 3.
• Even expand: left=1, right=2. s[1]='a', s[2]='b'. Mismatch. Result: "".

i=2, center 'b':

• Odd expand: left=2, right=2 -> s[1]='a' == s[3]='a' -> left=1, right=3 -> s[0]='b' != s[4]='d', exit. Return s[2:3]... retrace:
  • Start: left=2, right=2.
  • Iteration 1: s[2]='b' matches itself -> left=1, right=3.
  • Iteration 2: s[1]='a' == s[3]='a' -> left=0, right=4.
  • Iteration 3: s[0]='b' != s[4]='d' -> exit. Return s[1:4] = "aba". Length 3. Tied with "bab".
• Even expand: s[2]='b', s[3]='a'. Mismatch. "".

i=3 and i=4: expansions yield at most length 1 and 2. No improvement.

Final answer: "bab" (or "aba" — both valid, problem accepts either).

The key detail from the trace: the expand function returns s[left+1:right] because the loop exits only after left and right have overshot by one. At loop exit, s[left] and s[right] are the first mismatching characters (or one of them is out of bounds). The palindrome is always one step inside.

Approach 3: dynamic programming

The DP framing asks: when is s[i..j] a palindrome? Answer: when s[i] == s[j] and s[i+1..j-1] is also a palindrome. That recurrence defines a two-dimensional table.

Let dp[i][j] = True if s[i..j] is a palindrome. Base cases:

• Length 1: dp[i][i] = True for all i.
• Length 2: dp[i][i+1] = True iff s[i] == s[i+1].

Then fill upward by substring length, from 3 to n.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""
 
        # dp[i][j] = True means s[i..j] is a palindrome
        dp = [[False] * n for _ in range(n)]
        start = 0
        max_len = 1
 
        # every single character is a palindrome
        for i in range(n):
            dp[i][i] = True
 
        # length-2 substrings
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_len = 2
 
        # lengths 3 through n
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        start = i
                        max_len = length
 
        return s[start:start + max_len]

public class Solution {
    public string LongestPalindrome(string s) {
        int n = s.Length;
        if (n == 0) return "";
 
        bool[,] dp = new bool[n, n];
        int start = 0, maxLen = 1;
 
        // every single character
        for (int i = 0; i < n; i++)
            dp[i, i] = true;
 
        // length-2 substrings
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i, i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }
 
        // lengths 3 through n
        for (int length = 3; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s[i] == s[j] && dp[i + 1, j - 1]) {
                    dp[i, j] = true;
                    if (length > maxLen) {
                        start = i;
                        maxLen = length;
                    }
                }
            }
        }
 
        return s.Substring(start, maxLen);
    }
}

Time: O(n^2) — filling an n x n table with constant work per cell. Space: O(n^2) for the table itself. That is the cost: same asymptotic time as expand-from-center, but trading O(1) space for O(n^2).

The DP table for s = "babad" (5 x 5, True cells shown):

Filling order: all length-1 diagonals first, then length-2, then length-3. dp[0][2] becomes True because s[0]='b' == s[2]='b' and dp[1][1]=True. dp[1][3] becomes True because s[1]='a' == s[3]='a' and dp[2][2]=True. Both are length 3, so the answer is whichever update happened last — the code picks "aba" since dp[1][3] is the last length-3 True cell written.

Edge cases

Single character (s = "a"): the outer loop in expand runs zero iterations for odd (condition left >= 0 and right < n and s[left] == s[right] — both pointers start equal, so the single character matches itself and the loop runs once, then overshoots). The function returns "a". In DP, length-1 initialization sets dp[0][0] = True, max_len = 1, and no longer length is found.

All same characters (s = "aaaa"): expand from center 0 expands as far right as possible; from center 1 expands even further. The final answer is the full string "aaaa". In DP, every dp[i][j] entry is True (since s[i] == s[j] always and the inner substring is always a palindrome by induction). The last entry written for the maximum length captures the full string.

No palindrome longer than 1 (s = "abcde"): every expand returns a single character (the center) for odd and empty string for even. The longest remains length 1 — correctly the first character (or whichever the loop reaches last for length-1 palindromes; since every character qualifies and we only update on strictly longer, the answer is "a").

Even-length palindrome (s = "cbbd"): the critical center is the gap between indices 1 and 2 ('b' and 'b'). Even expand: left=1, right=2, s[1]='b' == s[2]='b' -> left=0, right=3. s[0]='c' != s[3]='d' -> exit. Returns s[2:3]... wait: s[left+1:right] = s[1:3] = "bb". Correct.

s with length 2, both equal (s = "aa"): even expand at i=0 gives "aa". Odd expand gives "a" for each character. The answer is "aa".

s with length 2, different (s = "ab"): all expansions yield single characters. Answer is "a".

Approach comparison

The pattern underneath both optimal approaches

Expand-from-center and the DP recurrence are expressions of the same fact: a palindrome is defined recursively. If s[i..j] is a palindrome, you know immediately that s[i+1..j-1] is also a palindrome. Equivalently, if you know s[i+1..j-1] is a palindrome, you just need s[i] == s[j] to extend it outward.

Expand-from-center builds on this by working outward from length 1: grow until you cannot. DP builds inward from the definition: fill small cases first, then use them to confirm larger ones. Same recurrence, opposite direction of computation.

This pattern is called "center-anchored palindrome expansion" and it transfers directly to the sibling problems below. Once you see a palindrome question, the first instinct should be: locate the centers, think about expansion. Substrings are the wrong unit of analysis; centers are the right one.

What I would actually ship

Expand-from-center. No contest. It has the same O(n^2) time as DP and O(1) space instead of O(n^2). The code is shorter and the logic is easier to explain in an interview: "I treat each position as a potential center and expand outward." The DP table is correct and pedagogically valuable — it builds intuition for tabulation — but it pays n^2 memory for nothing you actually need at runtime.

Brute force is the right starting point if you are stuck: implement it, confirm it works, then identify the redundancy. The gap from O(n^3) to O(n^2) is exactly one insight: stop checking substrings and start thinking about centers.

Where this sits in the DP series and what comes next

This is problem five in the dynamic-programming series, arriving after Climbing Stairs, House Robber, and Coin Change. Those earlier problems all had one-dimensional state — a single index advancing through a linear structure. Longest Palindromic Substring introduces two-dimensional DP state: dp[i][j] depends on dp[i+1][j-1]. That diagonal dependency is the new thing here, and it shows up again in the next few problems.

Palindromic Substrings (LeetCode 647) is the most direct extension. Same setup, different question: instead of the longest palindrome, count all of them. The expand-from-center structure is identical — you just count each successful expansion rather than comparing lengths. If this problem felt natural, 647 takes five minutes.

Longest Palindromic Subsequence (LeetCode 516) changes the rules: characters no longer need to be contiguous. Now dp[i][j] is the length of the longest palindromic subsequence in s[i..j]. The recurrence: if s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2; otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]). The diagonal-filling order from this problem applies directly.

Shortest Palindrome (LeetCode 214) asks: what is the minimum number of characters to add to the front of s to make it a palindrome? The insight is finding the longest palindromic prefix, which is a constrained version of this problem.

Edit Distance (LeetCode 72) also fills a 2D DP table with diagonal and adjacent dependencies — not palindromes, but the same spatial structure. Seeing how dp[i][j] depends on dp[i+1][j-1] here builds the intuition for why Edit Distance fills the way it does.