Palindromic Substrings

Moderate

0/80

Average time to solve is 20m

Contributed by

1 upvote

Asked in companies

Problem statement

You are given a string ‘S’. Your task is to return all distinct palindromic substrings of the given string in alphabetical order.

A string is said to be palindrome if the reverse of the string is the same as the string itself.

For Example:

Consider ‘S’ = ‘abba’, all the possible substrings are [ ‘a’, ‘ab’, ‘abb’, 'abba', 'b', ‘ba’, 'bb', ‘bba’ ] out of which [ ‘a’, ‘abba’, 'b’, 'bb'] are palindromic substrings.

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

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases.

The first and only line of each test case contains the string ‘S’.

Output Format:

For each test case, print all distinct palindromic substrings of the given string. Print the substrings in a sorted manner and they should be space-separated.    

Print the output of each test case in a separate line.

Note:

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

Constraints:

1 <= T <= 10
1 <= |S| <= 1000

String 'S' contains lowercase English letters only.

Time limit: 1 sec

Sample Input 1:

2
abba
bab

Sample Output 1:

a abba b bb
a b bab

Explanation:

For the first test case, all the possible substrings are [ ‘a’, ‘ab’, ‘abb’, 'abba', 'b', ‘ba’, 'bb', ‘bba’ ] out of which [ ‘a’, ‘abba’, 'b’, 'bb'] are palindromic substrings.

For the second test case, all the possible substrings are [‘a’, ‘ab’, ‘b’, ‘ba’, ‘bab’] out of which [‘a’, ‘b’, ‘bab’] are palindromic substrings.

Sample Input 2:

2
babbb
abcdc

Sample Output 2:

a b bab bb bbb
a b c cdc d

Approaches (1)

Approach 1

Solution using modified Manacher’s algorithm

Time Complexity

Space Complexity

(100% EXP penalty)

Palindromic Substrings

Console