Longest Palindromic Substring

Longest Palindromic Substring is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Expanding From Center (Palindromes) subpattern.

Problem statement

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.

Topics and companies

Topics: Two Pointers, String, Dynamic Programming.

Reported in interviews at Amazon, Microsoft, Wayfair, Facebook, Adobe, eBay, Google, Oracle, Goldman Sachs, Yandex, Qualcomm.

How to practise Longest Palindromic Substring on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Longest Palindromic Substring in the code editor, or read the Longest Palindromic Substring editorial for a worked solution with its approach and complexity analysis.

Where Longest Palindromic Substring sits in the DSA pattern sheet

• Two Pointers pattern guide
• Expanding From Center (Palindromes) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Longest Palindromic Substring

Other problems that use the same Expanding From Center (Palindromes) and Two Pointers techniques:

• Palindromic Substrings — Medium, same subpattern
• Backspace String Compare — Easy, same pattern
• Boats to Save People — Medium, same pattern
• Container With Most Water — Medium, same pattern
• Crawler Log Folder — Easy, same pattern
• Delete the Middle Node of a Linked List — Medium, same pattern