Skip to main content

18. Longest Palindromic Substring

mediumAsked at Udemy

Find the longest palindromic substring — Udemy uses expand-around-center to evaluate string manipulation instincts for search autocomplete features.

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

Problem

Given a string s, return the longest palindromic substring in s. If there are multiple answers of the same maximum length, return any one of them.

Constraints

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

Examples

Example 1

Input
s = "babad"
Output
"bab"

Example 2

Input
s = "cbbd"
Output
"bb"

Approaches

1. Brute force

Check every substring with an isPalindrome helper — O(n^3) time.

Time
O(n^3)
Space
O(1)
function longestPalindrome(s) {
  let best = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const sub = s.slice(i, j+1);
      if (sub === sub.split('').reverse().join('') && sub.length > best.length) best = sub;
    }
  }
  return best;
}

Tradeoff:

2. Expand around center

For each character (and each gap between characters) expand outward while the palindrome holds; track the widest found. O(n^2) time, O(1) space — the sweet spot Udemy expects.

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

Tradeoff:

Udemy-specific tips

Udemy asks about e-learning recommendation systems, content search, and marketplace algorithms — balanced mix of arrays, hash maps, and dynamic programming problems.

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

Practice these live with InterviewChamp.AI →