Unique Palindromic Substrings

Given a string s, find all unique palindromic substrings contained in s and output them in lexicographical (dictionary) order. A substring is a contiguous sequence of characters within a string. A palindrome is a string that reads the same backwards as forwards. The answer should include each palindromic substring exactly once.

Note: If the input string is empty, output nothing.

Input: A single line containing the string s.

Output: A single line containing the unique palindromic substrings sorted in lexicographical order and separated by a space.

Example:

Input: abaaa
Output: a aa aaa aba b

inputFormat

The input consists of a single line which is a string s. The string may contain alphanumeric characters and symbols. Its length can be assumed to be manageable for an O(n^2) solution.

outputFormat

Print a single line containing all unique palindromic substrings of s, sorted in lexicographical order. The substrings should be separated by a single space. If s is empty, print nothing.

abaaa

a aa aaa aba b