Skip to main content

15. Longest Palindromic Substring

mediumAsked at Gojek

Return the longest substring of s that is a palindrome.

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 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

Check every substring for palindrome property.

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

Tradeoff:

2. Expand around each center

A palindrome has a center between or on a character; from each center expand outward while characters match. Try both odd and even centers.

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

Tradeoff:

Gojek-specific tips

Gojek interviews on SEA-region payloads where strings carry multi-script characters; show you handle JS code unit indexing correctly so the algorithm survives the mobile-first edge.

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

Practice these live with InterviewChamp.AI →