New update is available. Click here to update.

Problem

Submissions

Solution

New

Discuss

Longest Palindromic Substring

Contributed by

Amandeep Kaur

Last Updated: 23 Feb, 2023

Easy

0/40

Avg time to solve 20 mins

Success Rate 80 %

61 upvotes

Problem Statement

Suggest Edit

You are given a string (STR) of length N.

Your task is to find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.

Note:

A substring is a contiguous segment of a string.

For example :

The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome. There is another palindromic substring of length 3 is "bab". Since starting index of "aba" is less than "bab", so "aba" is the answer.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run. 
Then the 'T' test cases follow.

The first and only one of each test case contains a string (STR).

Output Format :

For every test case, print a single line containing the longest palindromic substring. 

If there are multiple possible answers then you need to print the substring which has the lowest starting index.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Follow up:

Try to solve it using O(1) space complexity.

Constraints :

1 <= T <= 10
0 <= N <= 10^3

where 'T' is the number of test cases, 'N' is the length of the given string.

Time Limit: 1 sec

Sample Input 1:

1
abccbc

Sample Output 1:

bccb

Explanation for input 1:

For string "abccbc" there are multiple palindromic substrings like "a", "b", "c", "cc", "bccb", "cbc". But "bccb" is of the longest length. Thus, answer is "bccb".

Sample Input 2:

1
aeiou

Sample Output 2:

Explanation for input 2:

For string "aeiou" there are multiple palindromic substrings like "a", "e", "I", "o", "u", and all of the same length. But palindromic substring "a"  has the minimum starting index. Thus, the answer is "a".

Auto

Console

Dynamic Programming Notes

Min cost to reach N

Maximum sum of two non-overlapping subarrays of a given size

Optimal Strategy for a game

Edit Distance

Rod Cutting Problem

Longest Palindromic Substring

Palindrome Partitioning ll

Count ways to reach the nth stairs

Colorful Knapsack

Longest Palindromic Subsequence

Longest Palindromic Substring

Problem Statement

You are given a string (STR) of length N.

Your task is to find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.

Note:

For example :

Input Format:

Output Format :

Note :

Follow up:

Constraints :

Sample Input 1:

Sample Output 1:

Explanation for input 1:

Sample Input 2:

Sample Output 2:

Explanation for input 2: