Contents

1 Problem Statement

Please refer to the palindromic pangram problem on this page.

2 Analysis

Let {A}_{p} represent a word and let {A}_{pr} represent its reverse. Let {A}_{1}, {A}_{2}, ..., {A}_{n-1}, {A}_{n} be the subsequences of {A}_{pr} such that all of {A}_{1}, {A}_{2}, ..., {A}_{n-1} are valid words while {A}_{n} could be a valid word, but must be a palindrome. Then we can say that the following is a pangram for word {A}_{p}:

Let us verify if this holds true with the following two examples cited in the problem statement:

where {A}_{n} = ’d’ which is a palindrome, but not a valid word!

Similaraly,

where {A}_{n} = ’aya’ which is a palindraome, but not a valid word!

It can be easily observed here that {A}_{1}, {A}_{2},...,{A}_{n} are all prefixes of {A}_{pr}. Or we can think of them as substring q of string {A}_{pr}. We also know then that a suffix tree is a good data structure to do string matching!

2.1 Pangram containing all letters of the alphabet

Since there is no single word, that contains all letters of the alphabet, as such we have to merge pangrams to build one such that contains all letters. At the same time, the combination of two pangrams should keep it a pangram. The only way to do that is, to prefix and suffix one pangram to the other as follows:

If A and B are two words that are pangrams by the previous definition, then:

and

are both pangrams.

Thus applying this formula,

is also a pangram.

Thus we have now the raw material to define an algorithm that will find the shortest sequence of words that contains all letters, is a palindrome and a pangram.

3 Algorithm

• Build a suffix tree of the words in the dictionary.
• Now for each word in the dictionary, find it reverse. For the reverse word, find the prefixes that are actually words in the dictionary. If you can find matches for the entire reverse word, it implies it is a pangram. If it is a pangram, add the actual word and number of distinct characters in it to a list.
• Sort the pangrams by the distinct number of letters it contains.
• Now starting with the largest pangram, merge it with the next largest pangram that contains as many letters as possible that the largest pangram does not contain. Continue the merging process, till all letters of the alphabet are accounted for.
• All the pangrams found in the previous step can then be merged as explained in the previous section to find the palindromic pangram that contains all letters of the alphabet.