Coding

Longest Palindromic Substring

Asked at

Paytm

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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

A palindromic substring is a contiguous sequence of characters within the string that reads the same forward and backward.

**Input: **s = "babad" Output: "bab" Explanation: Both "bab" and "aba" are valid palindromic substrings of length 3. Return either.

Input: s = "cbbd" **Output: **"bb" Explanation: The longest palindrome is "bb" of length 2.

**Input: **s = "a12321b"

1 <= s.length <= 1000
s consists of only English letters (both lowercase and uppercase) and digits.

cpp

class Solution {
public:
    string longestPalindrome(string s) {
        // Your code goes here
    }
};

java

class Solution {
    public String longestPalindrome(String s) {
        // Your code goes here
    }
}

python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Your code goes here

javascript

class Solution {
    longestPalindrome(s) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public string LongestPalindrome(string s)
    {
        // Your code goes here
    }
}

func longestPalindrome(s string) string {

Stuck? Show a way to structure it+

01Consider both odd and even centers
02Expand while indices are valid and characters match
03Update best start and length after each expansion
04Return the best slice

Reference answer

Start by restating the input contract for Longest Palindromic Substring and testing the smallest boundary case before choosing the algorithm. Expand around every possible center: each character is an odd center and each gap is an even center. While both sides match, extend outward and retain the longest interval. This is simple, O(n^2) time, and O(1) extra space; Manacher is faster but rarely needed first. Explain the invariant while coding, then show how each update preserves it. State the complexity explicitly: use the notation appropriate to the chosen structure and include auxiliary space, not just runtime. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

When would you use Manacher's algorithm?
Tests: follow-up reasoning
How does DP compare in space?
Tests: complexity analysis

Hiring now

Paytm has 128 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer – Backend (Travel)
Bangalore, Karnataka
Junior Marketing Manager
Luxembourg
Collection Manager- North- Business- Lending Collections
Aligarh, Uttar Pradesh

Or practice this question first

Next question