Longest Palindromic Substring – Solution & Complexity

Q: What is the time and space complexity of Longest Palindromic Substring?

The optimal Longest Palindromic Substring solution runs in `O(n^2)` time and `O(1)` space. Expand around each center and keep the widest palindrome window seen.

Q: What is the most efficient way to solve Longest Palindromic Substring?

Expand around each center and keep the widest palindrome window seen. This gives `O(n^2)` time complexity, and is a classic strings and dynamic programming problem.

Q: How do you solve Longest Palindromic Substring in Python, JavaScript, Java, Go & Rust?

We provide a worked Longest Palindromic Substring solution in Python, JavaScript, Java, Go & Rust with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Longest Palindromic Substring an easy or hard interview question?

Longest Palindromic Substring is generally rated **Medium**. It tests strings and dynamic programming, which are common coding-interview patterns.

1. Choose an Approach

Checking every substring for being a palindrome is O(n^3).
The clean, interview-friendly optimum is to expand around every possible center in O(n^2) time and O(1) space.
A palindrome is fully described by its center, so we grow outward from each center and remember the longest match.

2. Expand Around a Center

From a center, move two pointers outward while the characters match and stay in bounds.
Return the start and end indices of the widest palindrome found for that center.

def expand(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # step back to the last matching pair
    return left + 1, right - 1

3. Track the Longest Over All Centers

There are 2n - 1 centers: one at each character (odd length) and one between each pair (even length).
For each center, expand and update the best (start, end) window whenever a longer palindrome is found.

def longest_palindrome(s: str) -> str:
    if not s:
        return ""
    start, end = 0, 0
    for i in range(len(s)):
        for l, r in (expand(s, i, i), expand(s, i, i + 1)):
            if r - l > end - start:
                start, end = l, r
    return s[start:end + 1]

4. Final Complete Solution

Each of the 2n - 1 centers expands at most O(n) times, so the total time is O(n^2).
We only store a couple of indices, so the extra space is O(1).

def longest_palindrome(s: str) -> str:
    if not s:
        return ""

    def expand(left: int, right: int) -> tuple[int, int]:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    start, end = 0, 0
    for i in range(len(s)):
        for l, r in (expand(i, i), expand(i, i + 1)):
            if r - l > end - start:
                start, end = l, r
    return s[start:end + 1]

Longest Palindromic Substring – Solution & Complexity

1. Choose an Approach

2. Expand Around a Center

3. Track the Longest Over All Centers

4. Final Complete Solution

FAQ

What is the time and space complexity of Longest Palindromic Substring?

What is the most efficient way to solve Longest Palindromic Substring?

How do you solve Longest Palindromic Substring in Python, JavaScript, Java, Go & Rust?

Is Longest Palindromic Substring an easy or hard interview question?