Skip to main content

33. Longest Palindromic Substring

mediumAsked at Ola

Find the longest palindromic substring of a string.

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

Problem

Given a string s, return the longest palindromic substring in s.

Constraints

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

Examples

Example 1

Input
s = "babad"
Output
"bab"

Example 2

Input
s = "cbbd"
Output
"bb"

Approaches

1. Check every substring

Enumerate substrings and check each for palindrome.

Time
O(n^3)
Space
O(1)
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].reverse().join('') && sub.length > best.length) best = sub;
  }
return best;

Tradeoff:

2. Expand around center

Try every position as a center (odd and even); expand outward while characters match.

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

Tradeoff:

Ola-specific tips

Ola interviewers ask the expand-around-center as a proxy for tight nested loop control; tie it to scanning a symmetric route-name string for branding patterns.

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

Practice these live with InterviewChamp.AI →