Problem

Submissions

Hints & solutions

Discuss

Longest Palindromic Substring

Moderate

0/80

Average time to solve is 20m

Contributed by

153 upvotes

Asked in companies

Problem statement

You are given a string 'str' of length 'N'.

Your task is to return the longest palindromic substring. If there are multiple strings, return any.

A substring is a contiguous segment of a string.

For example :

str = "ababc"

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 contains a string 'str'.

Output Format :

The output contains the size of the longest palindromic substring if that substring is the answer, else -1.

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.

Sample Input 1:

abccbc

Sample Output 1:

bccb

Explanation for input 1:

For string "abccbc",  there are several palindromic substrings such as "a", "b", "c", "cc", "bccb", and "cbc". However, the longest palindromic substring is "bccb".

Sample Input 2:

aeiou

Sample Output 2:

Constraints :

1 <= |str| <= 10^3

Time Limit: 1 sec

Hint 1

Hint 2

Hint 3

Think of brute force and try to generate all substring.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

Generate substrings of the given string such that substring having greater length will be generated first.
To do this, run a loop where iterator ‘LEN’ will go from N to 1, where N is the length of the given string.
Run a nested loop and fix an iterator ‘j’ that will point at the starting index of the substring.
Get the substring from ‘j’ to ‘j’ + ‘LEN’.
If the substring is a palindrome, return the substring (as the substring will be of the longest length and minimum starting index).

Time Complexity

O(N ^ 3), where ‘N’ is the length of the given string.

We are creating every substring which takes N ^ 2 time. Checking whether the substring is palindromic takes O(length of substring) time, which can be maximum O(N). Thus, the total time complexity is O(N ^ 3).

Space Complexity

O(N), where ‘N’ is the length of the given string.

We are storing substring in a variable string.

(100% EXP penalty)

Longest Palindromic Substring

Console