5. Longest Palindromic Substring (Medium)

Problem

Given a string s, return the longest palindromic substring in s.

Example

s = "babad" → "bab" (or "aba")
s = "cbbd" → "bb"

LeetCode 5 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, check every substring

For each substring, verify it’s a palindrome.

def longest_palindrome(s):
    def is_pal(t):
        return t == t[::-1]          # L1: O(len(t)) reversal + compare
    best = ""
    for i in range(len(s)):          # L2: outer loop over start indices
        for j in range(i, len(s)):   # L3: inner loop over end indices
            if is_pal(s[i:j + 1]) and j - i + 1 > len(best):  # L4: O(n) slice + is_pal
                best = s[i:j + 1]   # L5: O(n) slice copy
    return best

function longestPalindrome(s: string): string {
    function isPal(t: string): boolean {
        return t === t.split('').reverse().join('');  // L1: O(k) reversal + compare
    }
    let best = '';
    for (let i = 0; i < s.length; i++) {             // L2: outer loop over start indices
        for (let j = i; j < s.length; j++) {         // L3: inner loop over end indices
            const sub = s.slice(i, j + 1);
            if (isPal(sub) && sub.length > best.length) {  // L4: O(n) slice + isPal
                best = sub;                           // L5: O(n) slice copy
            }
        }
    }
    return best;
}

func longestPalindrome(s string) string {
    isPal := func(t string) bool {
        l, r := 0, len(t)-1
        for l < r {
            if t[l] != t[r] { return false }  // L1: O(k) compare
            l++; r--
        }
        return true
    }
    best := ""
    for i := 0; i < len(s); i++ {              // L2: outer loop over start indices
        for j := i; j < len(s); j++ {          // L3: inner loop over end indices
            sub := s[i : j+1]
            if isPal(sub) && len(sub) > len(best) {  // L4: O(n) compare
                best = sub                      // L5: O(n) slice copy
            }
        }
    }
    return best
}

final class Solution {
    func longestPalindrome(_ s: String) -> String { let c = Array(s); var best: [Character] = []; for i in c.indices { for j in i..<c.count { let part = Array(c[i...j]); if part.count > best.count && part == Array(part.reversed()) { best = part } } }; return String(best) }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (is_pal reversal)	$O(k)$ where k = substring length	once per (i,j) pair	$O(n)$ amortized per outer i
L2 (outer loop)	$O(1)$	n	$O(n)$
L3 (inner loop)	$O(1)$	$O(n)$ per outer i	$O(n²)$ iterations total
L4 (slice + is_pal)	$O(n)$	$O(n²)$ times	$O(n³)$ ← dominates
L5 (best update)	$O(n)$	at most n times	$O(n²)$ worst case

The bottleneck is L4: each of the $O(n²)$ substring pairs triggers an $O(n)$ palindrome check via slice and reversal. Slicing s[i:j+1] already copies $O(n)$ characters before the comparison even starts.

Complexity

Time: $O(n³)$ , driven entirely by L4 ( $O(n)$ palindrome check across $O(n²)$ pairs).
Space: $O(n)$ for the slice copies.

Approach 2: Expand around center (canonical)

Every palindrome has a center, a single character (odd length) or a pair (even length). For each of 2n - 1 centers, expand outward.

def longest_palindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:  # L1: O(1) per iteration, up to n/2 iters
            l -= 1                                       # L2: O(1)
            r += 1                                       # L3: O(1)
        return s[l + 1:r]                               # L4: O(length of palindrome found)

    best = ""
    for i in range(len(s)):                             # L5: outer loop, n iterations
        for cand in (expand(i, i), expand(i, i + 1)):  # L6: two expand calls per center
            if len(cand) > len(best):                   # L7: O(1)
                best = cand                             # L8: O(1) reference copy
    return best

function longestPalindrome(s: string): string {
    function expand(l: number, r: number): string {
        while (l >= 0 && r < s.length && s[l] === s[r]) {  // L1: O(1) per iteration
            l--;                                             // L2: O(1)
            r++;                                             // L3: O(1)
        }
        return s.slice(l + 1, r);                           // L4: O(length of palindrome)
    }

    let best = '';
    for (let i = 0; i < s.length; i++) {                   // L5: outer loop, n iterations
        for (const cand of [expand(i, i), expand(i, i + 1)]) {  // L6: two expand calls
            if (cand.length > best.length) {                // L7: O(1)
                best = cand;                                // L8: O(1)
            }
        }
    }
    return best;
}

func longestPalindrome(s string) string {
    expand := func(l, r int) string {
        for l >= 0 && r < len(s) && s[l] == s[r] {  // L1: O(1) per iteration
            l--                                       // L2: O(1)
            r++                                       // L3: O(1)
        }
        return s[l+1 : r]                            // L4: O(length of palindrome found)
    }
    best := ""
    for i := 0; i < len(s); i++ {                   // L5: outer loop, n iterations
        for _, cand := range []string{expand(i, i), expand(i, i+1)} {  // L6: two expand calls
            if len(cand) > len(best) {               // L7: O(1)
                best = cand                          // L8: O(1)
            }
        }
    }
    return best
}

final class Solution {
    func longestPalindrome(_ s: String) -> String { let c = Array(s); var best = (0, 0); func expand(_ a: Int, _ b: Int) -> (Int, Int) { var l = a, r = b; while l >= 0 && r < c.count && c[l] == c[r] { l -= 1; r += 1 }; return (l + 1, r - l - 1) }; for i in c.indices { for pair in [expand(i, i), expand(i, i + 1)] where pair.1 > best.1 { best = pair } }; return String(c[best.0..<(best.0 + best.1)]) }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L5 (outer loop)	$O(1)$	n	$O(n)$
L6 (two expand calls)	varies	2n total	see L1
L1 (expand while loop)	$O(1)$ per step	$O(n)$ total across all centers	$O(n²)$ ← dominates
L4 (slice result)	$O(k)$	2n calls	$O(n)$ total amortized
L7, L8 (best update)	$O(1)$	2n	$O(n)$

The key insight is that all expand calls together do at most $O(n²)$ work: each character can be the boundary of at most $O(n)$ distinct palindromes, and boundaries are never revisited per center. In the worst case (e.g., "aaaa...a"), every center expands all the way out, giving exactly $O(n²)$ character comparisons total.

Complexity

Time: $O(n²)$ , driven by L1 (total expand steps across all 2n-1 centers).
Space: $O(1)$ auxiliary (the returned slice is unavoidable output, not overhead).

Most interview-friendly. Short code, easy to reason about.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: DP table of palindrome flags

dp[i][j] = True iff s[i:j+1] is a palindrome. Fill by length: dp[i][j] = (s[i] == s[j]) and (length ≤ 2 or dp[i+1][j-1]).

def longest_palindrome(s):
    n = len(s)                                                # L1: O(1)
    if n <= 1:
        return s
    dp = [[False] * n for _ in range(n)]                     # L2: O(n²) table allocation
    best = s[0]

    for i in range(n):                                        # L3: O(n) diagonal init
        dp[i][i] = True                                       # L4: O(1)

    for length in range(2, n + 1):                            # L5: outer loop over substring length
        for i in range(n - length + 1):                       # L6: inner loop over start index
            j = i + length - 1                               # L7: O(1)
            if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]):  # L8: O(1) DP lookup
                dp[i][j] = True                              # L9: O(1)
                if length > len(best):
                    best = s[i:j + 1]                        # L10: O(n) slice copy
    return best

function longestPalindrome(s: string): string {
    const n = s.length;                                                          // L1: O(1)
    if (n <= 1) return s;
    const dp: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));  // L2: O(n²)
    let best = s[0];

    for (let i = 0; i < n; i++) dp[i][i] = true;                               // L3/L4: diagonal

    for (let length = 2; length <= n; length++) {                               // L5: length loop
        for (let i = 0; i <= n - length; i++) {                                 // L6: start index
            const j = i + length - 1;                                           // L7: O(1)
            if (s[i] === s[j] && (length === 2 || dp[i + 1][j - 1])) {        // L8: DP lookup
                dp[i][j] = true;                                                // L9: O(1)
                if (length > best.length) best = s.slice(i, j + 1);            // L10: O(n) slice
            }
        }
    }
    return best;
}

func longestPalindrome(s string) string {
    n := len(s)                                               // L1: O(1)
    if n <= 1 {
        return s
    }
    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)                              // L2: O(n²) table allocation
    }
    best := s[0:1]
    for i := 0; i < n; i++ {
        dp[i][i] = true                                      // L3/L4: diagonal init
    }
    for length := 2; length <= n; length++ {                 // L5: outer loop over substring length
        for i := 0; i <= n-length; i++ {                    // L6: inner loop over start index
            j := i + length - 1                             // L7: O(1)
            if s[i] == s[j] && (length == 2 || dp[i+1][j-1]) {  // L8: O(1) DP lookup
                dp[i][j] = true                             // L9: O(1)
                if length > len(best) {
                    best = s[i : j+1]                       // L10: O(n) slice copy
                }
            }
        }
    }
    return best
}

final class Solution {
    func longestPalindrome(_ s: String) -> String { let c = Array(s), n = c.count; var dp = Array(repeating: Array(repeating: false, count: n), count: n), start = 0, length = 1; for i in stride(from: n - 1, through: 0, by: -1) { for j in i..<n where c[i] == c[j] && (j - i < 2 || dp[i + 1][j - 1]) { dp[i][j] = true; if j - i + 1 >= length { start = i; length = j - i + 1 } } }; return String(c[start..<(start + length)]) }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L2 (table allocation)	$O(n²)$	1	$O(n²)$
L3 (diagonal init)	$O(1)$	n	$O(n)$
L5 (length loop)	$O(1)$	n-1	$O(n)$
L6 (start loop) + L8 (DP check)	$O(1)$	$O(n²)$ total (i,j) pairs	$O(n²)$ ← dominates
L10 (best update slice)	$O(n)$	at most n updates	$O(n²)$ worst case

The $O(n²)$ work is spread evenly: each of the $O(n²)$ substrings gets a constant-time DP cell fill (L8). The space cost is also $O(n²)$ for the table, which is why this approach loses to expand-around-center on space despite matching it on time. It earns its keep when the problem needs every dp[i][j] answer (e.g., problem 131 Palindrome Partitioning).

Complexity

Time: $O(n²)$ , driven by the $O(n²)$ DP cell fills at L6/L8.
Space: $O(n²)$ for the boolean table.

Worse on space than Approach 2; useful when you also need answers for every (i, j) (e.g., problem 131 Palindrome Partitioning).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Optional: Manacher’s $O(n)$

Manacher’s algorithm solves the problem in $O(n)$ ; it’s rarely expected in interviews but worth knowing.

Summary

Approach	Time	Space
All substrings	$O(n³)$	$O(n)$
Expand around center	$O(n²)$	$O(1)$
DP table	$O(n²)$	$O(n²)$
Manacher’s	$O(n)$	$O(n)$

Expand-around-center is the canonical interview answer. Same template solves problem 647 (Palindromic Substrings).

Test cases

# Quick smoke tests, paste into a REPL or save as test_005.py and run.
# Uses the canonical implementation (Approach 2: expand around center).

def longest_palindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l + 1:r]

    best = ""
    for i in range(len(s)):
        for cand in (expand(i, i), expand(i, i + 1)):
            if len(cand) > len(best):
                best = cand
    return best

def _run_tests():
    # LeetCode examples
    assert longest_palindrome("babad") in ("bab", "aba")
    assert longest_palindrome("cbbd") == "bb"
    # Edge cases
    assert longest_palindrome("a") == "a"
    assert longest_palindrome("ac") in ("a", "c")
    # Larger cases
    assert longest_palindrome("racecar") == "racecar"
    assert longest_palindrome("abacaba") == "abacaba"
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function longestPalindrome(s: string): string {
    function expand(l: number, r: number): string {
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            l--;
            r++;
        }
        return s.slice(l + 1, r);
    }
    let best = '';
    for (let i = 0; i < s.length; i++) {
        for (const cand of [expand(i, i), expand(i, i + 1)]) {
            if (cand.length > best.length) best = cand;
        }
    }
    return best;
}

console.assert(['bab', 'aba'].includes(longestPalindrome('babad')));
console.assert(longestPalindrome('cbbd') === 'bb');
console.assert(longestPalindrome('a') === 'a');
console.assert(['a', 'c'].includes(longestPalindrome('ac')));
console.assert(longestPalindrome('racecar') === 'racecar');
console.assert(longestPalindrome('abacaba') === 'abacaba');
console.log('all tests pass');

func longestPalindrome(s string) string {
    expand := func(l, r int) string {
        for l >= 0 && r < len(s) && s[l] == s[r] {
            l--
            r++
        }
        return s[l+1 : r]
    }
    best := ""
    for i := 0; i < len(s); i++ {
        for _, cand := range []string{expand(i, i), expand(i, i+1)} {
            if len(cand) > len(best) {
                best = cand
            }
        }
    }
    return best
}

func main() {
    r := longestPalindrome("babad")
    assert(r == "bab" || r == "aba")
    assert(longestPalindrome("cbbd") == "bb")
    assert(longestPalindrome("a") == "a")
    r2 := longestPalindrome("ac")
    assert(r2 == "a" || r2 == "c")
    assert(longestPalindrome("racecar") == "racecar")
    assert(longestPalindrome("abacaba") == "abacaba")
    fmt.Println("all tests pass")
}

Strings, palindrome-around-center traversal

Sequence DP, the prefix or position state pattern used for strings and ordered arrays.
Two Pointers, the two index invariant that shrinks or coordinates positions without nested loops.

5. Longest Palindromic Substring (Medium)

Problem

Try it yourself

Approach 1: Brute force, check every substring

Approach 2: Expand around center (canonical)

Approach 3: DP table of palindrome flags

Optional: Manacher’s O(n)O(n)O(n)

Summary

Test cases

Related data structures

Related concepts

Optional: Manacher’s $O(n)$