Skip to main content

18. Longest Palindromic Substring

mediumAsked at Nubank

Find the longest substring of s that reads the same forward and backward — Nubank uses expand-around-center to gauge whether you can avoid O(n^3) brute force under stress.

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

Problem

Given a string s, return the longest palindromic substring in s. A palindrome reads the same forward and backward.

Constraints

  • 1 <= s.length <= 1000
  • s consists of digits and English letters

Examples

Example 1

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

Example 2

Input
s = "cbbd"
Output
"bb"

Approaches

1. Brute force pair check

For every substring, verify it's a palindrome; track the longest seen.

Time
O(n^3)
Space
O(1)
// for i: for j>i: if s[i..j] palindrome and longer, save. O(n^3) which TLEs on n=1000.

Tradeoff:

2. Expand around center

For each index, expand both odd-length and even-length palindromes outward while characters match. 2n-1 centers, each expand is O(n).

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

Tradeoff:

Nubank-specific tips

Nubank will time-box this and watch whether you keep code clean under pressure — write the expand helper first, then loop, don't inline the two-pointer dance.

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 Nubank interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →