Longest Palindrome in a String

Given a string, find the longest substring that is a palindrome. This problem tests your ability to recognize patterns and efficiently search for optimal solutions within strings, a common task in text processing and bioinformatics.

stringdynamic programmingpalindromesubstring

Problem Statement

You are given a string text. Your task is to identify the longest palindromic substring within text. A palindromic substring is a sequence of characters that reads the same forwards and backward. Return the longest such substring. If multiple substrings of the same maximum length exist, return any one of them.

Example 1

Input: bananas

Output: anana

The longest palindromic substring in 'bananas' is 'anana'.

Example 2

Input: racecarparty

Output: racecar

The longest palindromic substring in 'racecarparty' is 'racecar'.

Constraints

-1 <= len(text) <= 1000
-text consists of lowercase English letters only

Brute Force Approach

The brute force approach is like checking every possible combination of start and end points in the string to see if the substring is a palindrome. Imagine you're at a buffet and you taste every single possible combination of food items to find the best one. This involves checking every possible substring, leading to a high time complexity.

TimeO(n^3)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem