Skip to content

Volume ITechnology

4.23.5 — Longest Palindromic Substring ​

LeetCode 5 · Medium · ★ Blind 75

The problem ​

Return the longest substring of s that reads the same forwards and backwards.

"babad"  →  "bab"   (or "aba" — either is accepted)
"cbbd"   →  "bb"

Up to 1,000 characters.

Restating the Problem: You are given a string s. Your job is to find the longest contiguous block of characters within s that reads identically forwards and backwards. We don't just want the length; we need to return the actual string.

Constraints to Note:

  • s.length is up to 1000. This is a big clue! An O(N^2) algorithm takes about 1,000,000 operations, which easily passes within 1 second.
  • s consists of only digits and English letters.

The brute force, and where it wastes work ​

The most naive approach is to generate every possible substring, and for each one, check if it's a palindrome.

  • There are O(N^2) possible substrings.
  • Checking if a substring of length L is a palindrome takes O(L) time, which is worst-case O(N).
  • Total time complexity: O(N^3).

With N = 1000, N^3 is 1,000,000,000 operations. This will very likely hit a Time Limit Exceeded (TLE) error. We need something faster, ideally O(N^2).

The pattern ​

Every palindrome has a centre. So instead of checking every substring, stand at each possible centre and push outwards while the characters match.

The catch is that there are two kinds of centre:

  • Odd length — a single character, like the a in "bab".
  • Even length — the gap between two characters, like between the two bs in "bb".

A string of n characters has n character-centres and n − 1 gap-centres, so 2n − 1 in total. Try them all.

Forgetting the even case is the most common bug in this problem, and it fails on "cbbd" — the answer "bb" has no middle character.

The solution ​

python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        best_start, best_len = 0, 0  # (1)

        def expand(lo: int, hi: int):  # (2)
            nonlocal best_start, best_len  # (3)
            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:  # (4)
                lo -= 1
                hi += 1
            # the loop overshot by one on each side
            length = hi - lo - 1  # (5)
            if length > best_len:  # (6)
                best_len = length
                best_start = lo + 1

        for i in range(len(s)):  # (7)
            expand(i, i)          # (8) odd centre: one character
            expand(i, i + 1)      # (9) even centre: the gap after it

        return s[best_start:best_start + best_len]  # (10)
ts
function longestPalindrome(s: string): string {
  let bestStart = 0, bestLen = 0;  // (1)

  function expand(lo: number, hi: number): void {  // (2)
    while (lo >= 0 && hi < s.length && s[lo] === s[hi]) { lo--; hi++; }  // (4)
    const len = hi - lo - 1;  // (5)
    if (len > bestLen) { bestLen = len; bestStart = lo + 1; }  // (6)
  }

  for (let i = 0; i < s.length; i++) {  // (7)
    expand(i, i);  // (8)
    expand(i, i + 1);  // (9)
  }

  return s.slice(bestStart, bestStart + bestLen);  // (10)
}

Line by line ​

(1) Remember the best palindrome found so far by where it starts and how long it is, not as a string.

(2) expand(lo, hi) grows a palindrome outward from a middle. Every palindrome is a mirror around its centre. So start at a centre and step outward while the two ends match.

(3) nonlocal lets the inner function change the two outer variables. Without it, assigning to best_len inside expand would create a new, separate variable.

(4) While both ends are inside the string and the two characters match, step both ends outward by one.

(5) The loop stops one step too far on each side. Either a pointer left the string, or the two characters did not match. So the palindrome is the stretch strictly between lo and hi, and its length is hi - lo - 1.

(6) A new longest palindrome. It starts at lo + 1, one step inside the overshoot.

(7) Try every position as a centre.

(8) An odd-length palindrome centred on one character, like "aba" around the b.

(9) An even-length palindrome centred on the gap after it, like "abba" around the middle gap. If the two characters differ, this returns at once with length 0.

(10) Cut the answer out once, at the end.

The off-by-one after the loop is the fiddly part, so derive it rather than guess. The while stops when the characters no longer match, which means lo and hi have each moved one step too far. The palindrome actually spans lo + 1 to hi - 1, and its length is (hi - 1) - (lo + 1) + 1 = hi - lo - 1.

expand(i, i + 1) handles the even case, and it needs no bounds check — if i + 1 is past the end, the while condition fails immediately and the length comes out as 0.

Track indices, not substrings. Slicing inside the loop would be O(n) per check and would make the whole thing O(n^3). This is the same discipline as 4.6.5.

Trace ​

Let's trace s = "babad".

  • i = 0 ('b')
    • expand(0, 0): lo=0, hi=0 ('b' == 'b') \rightarrow lo=-1, hi=1 (break). Length = 1. best_len = 1, best_start = 0.
    • expand(0, 1): lo=0, hi=1 ('b' != 'a') \rightarrow break. Length = 0.
  • i = 1 ('a')
    • expand(1, 1): lo=1, hi=1 ('a' == 'a') \rightarrow lo=0, hi=2 ('b' == 'b') \rightarrow lo=-1, hi=3 (break). Length = 3. best_len = 3, best_start = 0.
    • expand(1, 2): lo=1, hi=2 ('a' != 'b') \rightarrow break. Length = 0.
  • i = 2 ('b')
    • expand(2, 2): lo=2, hi=2 ('b' == 'b') \rightarrow lo=1, hi=3 ('a' == 'a') \rightarrow lo=0, hi=4 ('b' != 'd') \rightarrow break. Length = 3. best_len = 3.
    • ...and so on.

The maximum length found is 3, starting at index 0. The substring s[0:3] is "bab".

Edge cases ​

  • One character. It is its own longest palindrome.
  • No two equal neighbours, like "abc". The answer is any single character, here the first.
  • The whole string is a palindrome. The middle centre expands to both ends.
  • Even-length answers, like "cbbd", whose answer is "bb". Found only because of line (9).

Complexity ​

O(n^2) time, O(1) space.

Time Complexity Derivation: We loop through n characters. At each character, we consider 2 centres (the odd and the even). That gives 2n - 1 centres to check. For each centre, the while loop expands outward until a mismatch is found. In the worst case (e.g., "aaaaa"), a centre expands up to n/2 steps. Therefore, (2N) \times (N/2) = N^2, making the total time O(N^2).

Space Complexity Derivation: We only store two integer variables: best_start and best_len. The expand function just uses local integer variables lo and hi. No auxiliary arrays or hash maps are allocated. Thus, O(1) extra space. This is the real advantage over the DP version below.

The DP version, and why it is worse here ​

This problem is filed under dynamic programming, so here is the DP, and here is why you should not write it.

Let dp[i][j] be true when s[i..j] is a palindrome:

dp[i][j] = (s[i] = s[j]) \ \text{and}\ \big(j - i < 2 \ \text{or}\ dp[i+1][j-1]\big)

The ends match, and the inside is already known to be a palindrome. The j - i < 2 covers lengths 1 and 2, which have no inside.

python
n = len(s)
dp = [[False] * n for _ in range(n)]
best = (0, 1)
for j in range(n):
    for i in range(j, -1, -1):                    # i counts DOWN
        if s[i] == s[j] and (j - i < 2 or dp[i+1][j-1]):
            dp[i][j] = True
            if j - i + 1 > best[1]:
                best = (i, j - i + 1)
return s[best[0]:best[0] + best[1]]

The loop order is the whole difficulty. dp[i][j] reads dp[i+1][j-1] — a larger i and a smaller j — so i must count downwards while j counts upwards, or you read cells that are not filled yet. That ordering question is the thing 2-D DP is really about, and it is covered properly in 4.24.

O(n^2) time and O(n^2) space.

Same time, far more memory, more code, and an ordering trap. Centre expansion wins on every count. Write it, and mention the DP as the version that generalises — because the table is genuinely useful in 4.18.7 Palindrome Partitioning, where you need to test many substrings rather than find one.

That is the real lesson: precompute a table when you will query it repeatedly; expand from centres when you need one answer.

Manacher's algorithm ​

There is an O(n) solution. It runs centre expansion but reuses information from palindromes already found, so a centre inside a known palindrome starts from a lower bound instead of from zero — the same "the pointer only moves forward" argument as the sliding window and the monotonic stack.

It is intricate and almost never expected. Name it, say it is O(n), and move on. 4.31 builds it properly.

Where this goes next ​

  • Palindromic Substrings — count them all instead of finding the longest. The identical expansion with a counter. 4.23.6.
  • Longest Palindromic Subsequence — a completely different problem, because gaps are allowed. It is genuinely 2-D DP, and it equals the longest common subsequence of the string and its reverse. 4.24.
  • Palindrome Partitioning II — the fewest cuts, which needs the DP table.

Substring means no gaps; subsequence allows gaps. Confusing them changes the algorithm completely, so read the problem statement twice.

What the interviewer will push on ​

"How many centres are there?" 2n − 1. Explain the even case, and say what "cbbd" does to a solution that misses it.

"Derive the length after expansion." The loop overshoots by one on each side, so it is hi - lo - 1.

"Can you do better than O(n^2)?" Manacher's, O(n). Naming it is enough.

"Why not DP?" Same time, O(n^2) space instead of O(1), and a loop-order trap. Then say when the table is worth building.

"What about the longest palindromic subsequence?" Different problem — 2-D DP, and it is LCS with the reversed string.

One thing to volunteer: say the centre count and the even-centre case before writing anything. It is the one place this problem is designed to catch you.

Next: 4.23.6 Palindromic Substrings — the same expansion, counting instead of measuring.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet