Is Longest Palindromic Substring easy or hard?

Longest Palindromic Substring is classified as a Medium problem. The brute force idea is simple, but recognizing the center-expansion insight or building a correct DP table requires stronger string and algorithmic reasoning.

How to solve Longest Palindromic Substring in O(n)?

Manacher’s algorithm solves the problem in linear time by transforming the string and reusing previously computed palindrome radii. It avoids redundant comparisons by leveraging symmetry around known centers. The algorithm runs in O(n) time and O(n) space but is more complex than typical interview solutions.

Longest Palindromic Substring Python or Java solution?

Python and Java implementations usually follow the Expand Around Center technique. For each index, the algorithm expands outward for both odd and even centers and tracks the longest valid substring. This implementation runs in O(n^2) time with constant extra space.

What is the best approach for Longest Palindromic Substring?

Expand Around Center is the most practical approach. It checks palindromes by expanding two pointers outward from every possible center in the string. The algorithm runs in O(n^2) time and O(1) space while remaining simple enough to implement quickly during interviews.

Is Longest Palindromic Substring asked at Google/Amazon/Meta?

Longest Palindromic Substring frequently appears in technical interviews at large tech companies including Google, Amazon, Meta, and Microsoft. Interviewers typically expect the Expand Around Center solution and may discuss the tradeoffs between it and Dynamic Programming.

What data structure is used in Longest Palindromic Substring?

The problem mainly uses string traversal with two-pointer expansion. In the Dynamic Programming approach, a 2D boolean table stores whether substring s[i..j] is a palindrome. No advanced data structures are required for the optimal interview solution.

What is the time complexity of Longest Palindromic Substring?

Most standard solutions run in O(n^2) time. Expand Around Center checks up to 2n centers and expands outward, while Dynamic Programming evaluates every substring once. The optimal theoretical solution, Manacher’s algorithm, achieves O(n) time.

Description Hints 3 Solution Video 8:11

5. Longest Palindromic Substring

Medium38.7% acceptance81 companies

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

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

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

Asked at top 20 of 81 companies

Cisco HSBC Maq Software Nielsen Commvault Earnin Hpe Bending Spoons Softwire Zemoso Mphasis Bloomberg

+8 more

Zoho Visa PhonePe Wix Cognizant EPAM Systems Tinkoff Huawei

Topics

Hints open one at a time

Hint 1

How can we reuse a previously computed palindrome to compute a larger palindrome?

Hint 2

If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?

Hint 3

Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.

8:11

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution