Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 5. Longest Palindromic Substring

Given a string s, return the longest substring that reads the same forwards and backwards. The core challenge is efficiently finding palindromic spans around centers (handling odd/even lengths); typical approaches are expand-around-center (O(n^2)) or Manacher's algorithm (O(n)), with n ≤ 1000.

Asked at:

Uber

DESCRIPTION

Input:

s = "babad"

Output:

"bab"

Explanation: Both "bab" and "aba" are valid longest palindromic substrings with length 3

Constraints:

1 <= s.length <= 1000
s consists of only lowercase English letters
Multiple valid answers may exist; return any one

Understanding the Problem

Let's understand what we're being asked to do. Given a string like 'babad', we need to find the longest substring that reads the same forwards and backwards.

Tracing through: 'bab' is a palindrome (reads same both ways), 'aba' is also a palindrome, but 'bad' is not (backwards is 'dab'). Both 'bab' and 'aba' have length 3, so either is a valid answer.

Important constraint: A palindrome can have odd length (like 'aba' with center 'b') or even length (like 'abba' with center between the two 'b's). We need to handle both cases!

Edge cases to consider: What if the entire string is a palindrome? What if no palindrome exists longer than 1 character? What if the string has length 1?

Brute Force Approach

The brute force approach generates all possible substrings and checks each one to see if it's a palindrome. For each starting position, try all possible ending positions, extract the substring, and verify if it reads the same forwards and backwards. Keep track of the longest palindrome found. This approach is simple but inefficient because it examines every possible substring.

Visualization

def longest_palindrome(s):
    """
    Find the longest palindromic substring using brute force.
    Check every possible substring to see if it's a palindrome.
    """
    if not s:
        return ""
    
    longest = ""
    n = len(s)
    
    # Try every possible starting position
    for start in range(n):
        # Try every possible ending position from this start
        for end in range(start, n):
            # Extract substring
            substring = s[start:end + 1]
            
            # Check if this substring is a palindrome
            is_palindrome = True
            left = 0
            right = len(substring) - 1
            
            while left < right:
                if substring[left] != substring[right]:
                    is_palindrome = False
                    break
                left += 1
                right -= 1
            
            # Update longest if this palindrome is longer
            if is_palindrome and len(substring) > len(longest):
                longest = substring
    
    return longest

Start finding longest palindromic substring

0 / 117

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n³) There are O(n²) possible substrings, and checking if each substring is a palindrome takes O(n) time, resulting in O(n³) total time

Space Complexity: O(1) Only constant extra space is needed for tracking the longest palindrome found

Building Intuition

Every palindrome has a center point from which it expands symmetrically. For 'aba', the center is 'b'. For 'abba', the center is between the two 'b's.

This means we can check each possible center position and expand outward while characters match, rather than checking every possible substring.

By expanding around centers, we avoid checking all possible substrings. Instead of examining every start-end pair (which would be O(n²) pairs, each taking O(n) to verify), we check O(n) possible centers and expand each in O(n) time.

This transforms a potentially O(n³) brute force approach into an O(n²) solution.

Think of dropping a pebble in water - ripples expand outward symmetrically. A palindrome works the same way: from a center, characters must match as you move outward.

For a string of length n, there are 2n-1 possible centers: n single-character centers (odd-length palindromes) and n-1 between-character centers (even-length palindromes). Check each center and expand while characters match.

Common Mistakes

Forgetting to handle even-length palindromes - you need to check both single-character centers and between-character centers

Off-by-one errors when expanding - make sure to check bounds before accessing characters at left-1 and right+1

Not tracking the actual substring indices - remember to store the start and length of the longest palindrome, not just its length

Inefficient substring extraction - avoid creating substring objects during expansion; only extract the final result

Assuming there's always a palindrome longer than 1 character - every single character is a valid palindrome of length 1

Optimal Solution

The optimal approach uses the expand-around-center technique. For each possible center position (both single characters for odd-length palindromes and between characters for even-length palindromes), expand outward while the characters on both sides match. Track the longest palindrome found during all expansions. This efficiently finds palindromes by leveraging their symmetric property without checking every possible substring.

Visualization

def longest_palindrome(s):
    """
    Find the longest palindromic substring using expand-around-center.
    Time: O(n^2), Space: O(1)
    """
    if not s:
        return ""
    
    # Track the longest palindrome found
    start = 0
    max_len = 0
    
    # Helper function to expand around center
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # Return length of palindrome
        return right - left - 1
    
    # Check each possible center
    for i in range(len(s)):
        # Odd length palindromes (single character center)
        len1 = expand_around_center(i, i)
        # Even length palindromes (between two characters)
        len2 = expand_around_center(i, i + 1)
        
        # Get the longer palindrome
        current_len = max(len1, len2)
        
        # Update if we found a longer palindrome
        if current_len > max_len:
            max_len = current_len
            # Calculate start position of palindrome
            start = i - (current_len - 1) // 2
    
    # Extract and return the longest palindrome
    return s[start:start + max_len]

Start finding longest palindromic substring

0 / 50

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) There are O(n) possible centers, and each expansion can take up to O(n) time in the worst case (when the entire string is a palindrome), resulting in O(n²) time

Space Complexity: O(1) Only constant extra space is needed for tracking indices and the longest palindrome

What We've Learned

Expand-around-center technique: Palindromes have natural symmetry around a center point - instead of checking every substring, expand outward from each possible center (O(n) centers × O(n) expansion = O(n²)). This transforms a naive O(n³) brute-force into an efficient O(n²) solution by exploiting structural properties.
Odd vs even length handling: Palindromes can have either a single-character center (odd length like "aba") or a two-character center (even length like "abba") - you must check both cases at each position by calling expand with (i, i) and (i, i+1) to avoid missing half of all possible palindromes.
Two-pointer expansion pattern: Use left and right pointers moving outward while characters match (while left >= 0 && right < n && s[left] == s[right]) - this bounded expansion naturally handles edge cases and stops at the first mismatch, giving you the exact palindrome boundaries.
String slicing vs index tracking: Instead of creating substrings during expansion (expensive), track only the start index and maximum length found - only slice once at the end using s.substring(maxStart, maxStart + maxLen) to avoid O(n) string copies in the inner loop.
Center-based optimization over DP: While dynamic programming works (O(n²) time, O(n²) space), expand-around-center achieves the same time complexity with O(1) space by computing palindromes on-demand rather than storing a full DP table - prefer space-efficient solutions when time complexity is equivalent.
Pattern recognition for symmetry problems: Whenever a problem involves finding symmetric structures (palindromes, mirror patterns, balanced sequences), consider center-expansion or two-pointer approaches - symmetry naturally suggests working from the middle outward or edges inward rather than left-to-right scanning.

Test Your Understanding

Why is string the right data structure for this problem?

string provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late November, 2025

Uber

Senior

https://leetcode.com/problems/longest-palindromic-substring/description/

Late November, 2025

Uber

Staff

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 5. Longest Palindromic Substring

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact