Skip to main content

32. Longest Palindromic Substring

mediumAsked at Postman

Find the longest palindromic substring within a given string.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string s, return the longest palindromic substring in s. If multiple have the same length, any one is acceptable.

Constraints

  • 1 <= s.length <= 1000
  • s consists of printable ASCII

Examples

Example 1

Input
s = "babad"
Output
"bab" (or "aba")

Example 2

Input
s = "cbbd"
Output
"bb"

Approaches

1. Check every substring

Enumerate every (i, j) and check whether s[i..j] is a palindrome.

Time
O(n^3)
Space
O(1)
// for i,j in nested loops: isPalindrome via two pointers

Tradeoff:

2. Expand around center

For each index, expand outward for both odd-length and even-length centers; track the longest. O(n^2) time, O(1) space.

Time
O(n^2)
Space
O(1)
function longestPalin(s) {
  let start = 0, len = 1;
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    const newLen = r - l - 1;
    if (newLen > len) { len = newLen; start = l + 1; }
  };
  for (let i = 0; i < s.length; i++) {
    expand(i, i);
    expand(i, i + 1);
  }
  return s.slice(start, start + len);
}

Tradeoff:

Postman-specific tips

Postman cares about the dual-center idiom (odd + even) — it's the same kind of edge-case discipline they expect for URL parsers handling both with-port and without-port forms.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Longest Palindromic Substring and other Postman interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →