Longest Palindromic Substring in Python and TypeScript

The Problem

You are given a string s. Return the longest substring of s that is a palindrome, meaning it reads the same from left to right as from right to left. A substring has to be contiguous: you cannot skip characters.

Example 1

Input: "bananas". Output: "anana". The five characters mirror each other around the middle n, and nothing longer does.

Example 2

Input: "noonday". Output: "noon". This palindrome has an even length, so its centre sits between the two o characters rather than on one of them. That detail is the trap in this question.

Assumptions to confirm

• If two palindromes tie for longest, can you return either? Usually yes.
• Is the input case-sensitive, and can it contain spaces or punctuation? Assume yes and compare characters exactly unless told otherwise.
• What should an empty string return? An empty string is the natural answer.

Brute Force First

The naive approach checks every substring. There are about n²/2 substrings, and checking whether each one is a palindrome takes up to O(n), so the total is O(n³) time. It works for short strings and it is easy to explain, which is exactly why you should say it out loud before optimising.

Interviewers want to hear the brute force because it shows you understand the problem fully and gives you a baseline to improve on. Spend thirty seconds on it, give its complexity, then explain where the waste is: you keep re-checking characters you have already compared.

The Optimal Approach: Expand Around Centre

Python and TypeScript Solutions

Python

def longest_palindrome(s: str) -> str:
    if len(s) < 2:
        return s
    start, best_len = 0, 1

    def expand(left: int, right: int) -> None:
        nonlocal start, best_len
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        length = right - left - 1
        if length > best_len:
            start, best_len = left + 1, length

    for i in range(len(s)):
        expand(i, i)      # odd length, centred on s[i]
        expand(i, i + 1)  # even length, centred between s[i] and s[i+1]
    return s[start:start + best_len]

TypeScript

function longestPalindrome(s: string): string {
  if (s.length < 2) return s;
  let start = 0;
  let bestLen = 1;

  const expand = (left: number, right: number): void => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    const length = right - left - 1;
    if (length > bestLen) {
      start = left + 1;
      bestLen = length;
    }
  };

  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // odd length, centred on s[i]
    expand(i, i + 1); // even length, centred between s[i] and s[i + 1]
  }
  return s.slice(start, start + bestLen);
}

Both versions store only a start index and a length, so the string is sliced once at the end. Expanding a centre stops as soon as characters differ, which is why the average case is much faster than the worst case.

Complexity Compared

How to Talk Through It in an Interview

A short script you can adapt:

1. Clarify: "So I return the substring itself, not its length, and any of several tied answers is fine?"
2. Brute force: "I could check every substring, which is O(n³). The waste is re-comparing the same characters."
3. Optimise: "Every palindrome mirrors around a centre, and there are 2n − 1 centres including the gaps. If I expand from each one, I get O(n²) time with constant space."
4. Code: write the helper that expands, then the loop that calls it twice per index. Say why you track start and length instead of strings.
5. Test: walk through "abba" to show the even centre works, then "a" and the empty string.

Edge Cases and Follow-Ups

Practise It in a Mock Coding Round

Reading a solution is not the same as producing it with someone watching. In a real round you have to clarify the problem, say the brute force out loud, and keep talking while you type. MockIF runs coding rounds with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, follows up on edge cases and complexity, then scores the round and gives you specific feedback. A session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing). Read more about how a mock coding interview works.

Frequently Asked Questions