Living on a Prayer

Judge Solution Idea:

Find the ending/starting positions of all distinct palindromic substrings using Palindromic Tree (Err Tree). Sort all of them. To design the comparator function of sorting, consider two distinct substrings. You know only their starting and ending positions (and length), now you need to check which of them is lexicogrpahically smaller. To do so, you can find the last position of the substrings upto which they match in log2(length) using hashing and binary search. Which one is lexicographically smaller will depend on the next position.

Alternate Solution: Manacher + Hashing