First of all, thanks to all who posted your solutions (publicly or
I got solutions from: Steve Kass, Adam Machanic, Rob Farley,
Maciej Pilecki and FoxTrot.
I got two types of solutions:
1. Brute Force method - generating all possible sentences, then filtering only
the ones that are palindromes. This logic allows for a very short and simple
solution query, but is extremely inefficient.
2. Constructing sentences from the edges, going inwards, and this way not
pursuing sentences that are known not to have potential to become
The winners would have to be Adam Machanic, Rob Farley and Steve
all three used the second approach.
Here's an example for a solution based on the Brute Force method:
with c as ( select cast(' ' + word + ' ' as varchar(max)) as sentence from words union all select c.sentence + w.word + ' ' from c join words as w on c.sentence not like '% ' + w.word + ' %' ) select rtrim(ltrim(sentence)) as palindrome from c where replace(sentence, ' ', '') = reverse(replace(sentence, ' ', ''));
The nice thing about the brute force solution is of course that it's short
and simple. But it's extremely slow.
For n words, the brute force solution generates the following number of
sentences (before the outer query filters palindromes):
n + n*(n-1) + n*(n-1)*(n-2) + ... + n!
To illustrate how big those numbers can be, here's a recursive CTE that
calculates the number of sentences produced out of n unique words:
with c as ( select n as words, cast(n as bigint) as sentences, cast(n as bigint) as v, n-1 as i from nums -- auxiliary table of numbers where n = 1 ) select words, sentences from c where i = 0 order by words; words sentences ----------- -------------------- 1 1 2 4 3 15 4 64 5 325 6 1956 7 13699 8 109600 9 986409 10 9864100 11 108505111 12 1302061344 13 16926797485 14 236975164804 15 3554627472075 16 56874039553216 17 966858672404689 18 17403456103284420 19 330665665962403999 20 6613313319248080000
I think that the brute force solution is a good example to use for teaching
purposes to describe the logic of recursive queries.
As for the more efficient method (constructing sentences from the edges,
going inwards), following are the solutions that I got.
I used the following sample data to test the performance of the solutions:
create table words(word varchar(50) not null primary key); insert into words values('even'); insert into words values('never'); insert into words values('odd'); insert into words values('or'); insert into words values('r'); insert into words values('e'); insert into words values('n'); insert into words values('er'); insert into words values('madam'); insert into words values('adam');
Solution by Steve Kass (165 ms):
create function ends( @lft varchar(200), @rgt varchar(200), @used varchar(8000) ) returns table as return with WW(w1word,w1wordX,w2word,w2wordX) as ( select w1.word,@lft+w1.word,w2.word,[email protected] from words as w1, words as w2 where substring(@lft+w1.word,1,len(w2.word+[email protected])) = substring(reverse([email protected]),1,len(@lft+w1.word)) and (w2.word w1.word) and @used not like '%\[ *\]'+w1.word+'\[ *\]%' and @used not like '%\[ *\]'+w2.word+'\[ *\]%' ), T(w,p,good,side,used) as ( select w1wordX+w2wordX as w, left(w1wordX,len(w2wordX)) + '.' + right(w2wordX,len(w1wordX)) as p, len(substring(w1wordX,1,len(w2wordX))) as good, sign(len(w2wordX)-len(w1wordX)) as side, replace(@used,'*',' '+w1word+'*'+w2word+' ') as used from WW union all select @[email protected], @[email protected], len(@[email protected])/2, 0, replace(@used,'*',' '+word+' ') from words where @[email protected] = reverse(@[email protected]) and @used not like '%\[ *\]'+word+'\[ *\]%' ) select *, substring(w,good+1,len(w)-2*good) as middle from T go with S(w,p,good,side,used,middle) as ( select * from ends('','','*') union all select E.* from S cross apply ends( parsename(S.p,2)+case when side=-1 then middle else '' end, case when side=1 then middle else '' end + parsename(S.p,1), S.used ) as E ) select replace(rtrim(ltrim(used)),'*',' ') from S where middle = reverse(middle) go
Steve's description of the solution:
"It first finds single words that are palindromes or pairs of
words that could be the leftmost and rightmost words in a
palindrome, such as "odder do" or "re bracer" For this to
be possible, left(first,minLen) = left(reverse(second),minLen)
where minLen is the minimum length of the two words.
To fill in "odder do" to a palindrome, we need to find words
that fit between odder and do that make a palindrome if
"der" (the unpaired middle) is appended to the left of those
One way to start is by finding all possible single or double
words ending in red and having an appropriate variation of the
property above, so that they still can be extended inward to
a palindrome. For example, inserting "oblate bored" is ok,
because all the new mismatch occurs in oblate. On the other
hand, inserting "cat tarred" does not work, because the
sentence "odder cat tarred do" cannot be made a palindrome
by adding words in the middle. The c and the r will never
The ends() function finds appropriate single or double words
that can take a potential palindrome and make it closer to one
(based on number of characters from each end that match).
I start with nothing, so there is no unmatched @lft or @rgt, nor
@used (which holds used words). That's the base case of the
recursive query. Then for every potential palindrome found,
@lft or @rgt is identified, and @used is, so when ends() is
invoked again, it finds fill-ins for the existing mismatch
in that potential palindrome. Because we need a table of
fill-ins for each potential palindrome, and to do this,
ends() needs information specific to that potential palindrome
(the @lft or @rgt along with the @used string of used words)
a CROSS APPLY is the appropriate way to go.
Once there are no more possible fill-ins, there will be both
incomplete and complete palindromes in the table. The complete
ones are those for which @[email protected] is itself a palindrome,
so that ' is a solution for the fill-in, meaning that the
potential palindrome is already a palindrome."
Solution by Adam Machanic (41 ms):
with n as ( select convert(varchar(1000), a.word) as parta, convert(varchar(1000), b.word) as partb, convert(varchar(1000), a.word) as repparta, convert(varchar(1000), reverse(b.word)) as reppartb from words a, words b where a.word b.word and ((len(a.word) > len(b.word) and a.word like reverse(b.word) + '%') or (reverse(b.word) like a.word + '%')) union all select convert(varchar(1000), case when len(repparta) > len(reppartb) then parta when len(repparta) len(repparta) then partb when len(repparta) > len(reppartb) then w.word + ' ' + partb when p.n = 1 then partb else w.word + ' ' + partb end) as partb, convert(varchar(1000), replace(case when len(repparta) > len(reppartb) then parta when len(repparta) len(repparta) then partb when len(repparta) > len(reppartb) then w.word + ' ' + partb when p.n = 1 then partb else w.word + ' ' + partb end, ' ', ''))) from n cross join words w cross apply ( select 1 union all select 2 where len(repparta) = len(reppartb) ) p(n) where case when ' ' + parta + ' ' + partb + ' ' not like '% ' + word + ' %' then case when len(repparta) > len(reppartb) then case when len(word) > len(repparta)-len(reppartb) then case when right(word, len(repparta)-len(reppartb)) = right(repparta, len(repparta)-len(reppartb)) then 1 else 0 end else case when word = substring(repparta, len(reppartb)+1, len(word)) then 1 else 0 end end when len(reppartb) > len(repparta) then case when len(word) > len(reppartb) - len(repparta) then case when left(word, len(reppartb)-len(repparta)) = substring(reppartb, len(repparta)+1, len(reppartb)-len(repparta)) then 1 else 0 end else case when word = substring(reppartb, len(repparta)+1, len(word)) then 1 else 0 end end else 1 --equal end else 0 end = 1 ) select final from ( select distinct rtrim(ltrim(parta + ' ' + partb)) final from n ) m where replace(final, ' ', '') = reverse(replace(final, ' ', '')) union all select word from words where word = reverse(word)
Adam's description of the solution:
"Much like the other solutions, the goal here is to build the palindrome
the outside in. The anchor part of the recursive CTE finds all pairs in the
words table, then finds the shorter word and uses it in a LIKE predicate
against the longer word. The solution I discovered is to always reverse the
rightmost word/group of words in the list: If the two words are "abcd" and
"cba", the predicate 'abcd' LIKE REVERSE('cba') + '%' is true. Likewise, if
the words are "abc" and "dcba", the predicate REVERSE('dcba') LIKE 'abc' +
'%' is true. Based on these, the anchor part finds potential palindromes.
The recursive part continues this logic in a slightly different way. It
uses a cross-join to the Words table to get all combinations of words with
the input set. The case expression does the following: First, it makes sure
that the given word has not already been used in the input set. Next, it
determines whether the right part or left part is longer. The same basic
logic is used in both cases, so we'll follow the right part being longer.
Assume that the two parts are: "abc" and "dcba". The difference is one
character, and that character is "d". The logic is to append any possible
words onto the left part, so the CASE expression finds all words in this
case that start with the letter "d". There is also a special case for the
differential being longer than the input. For instance, if the two parts
were "abc" and "gfedcba", and the word being compared were "de", that should
be a match. In that case, the expression looks at only as many characters
in the difference as the number of characters in the input word.
Finally, there is a special case for if the two input words are equal in
length. If so, a new row will be generated using the CROSS APPLY operator
(using the correlation name P). If the input set has the parts "abc" and
"cba", the idea is that any possible word could be a seed for a new
palindrome, appended to either the right or left part. So if the lengths are
equal and P.n = 1, the input word is appended to the left part. Otherwise,
it's appended to the right part.
After all of the recursion is done, the outer query does a final check to
determine whether or not each row is a palindrome. This final set is
unioned with any single words in the table that are, themselves, palindromes
(checked using REVERSE)."
Solution by Rob Farley (22 ms):
with pals as ( --Base select cast('' as varchar(max)) as startchars, cast('' as varchar(max)) as endchars, cast(' ' as varchar(max)) as startwords, cast(' ' as varchar(max)) as endwords union all --Sides even, so find a suitable word select startchars + w.word, endchars, startwords + w.word + ' ', endwords from pals p cross join words w where len(p.startchars) = len(p.endchars) and exists (select * from words w2 where w.word like reverse(w2.word) + '%' or reverse(w2.word) like w.word + '%') and startwords not like '% ' + w.word + ' %' and endwords not like '% ' + w.word + ' %' union all --Right longer than left, so find a word for there select startchars + w.word, endchars, startwords + w.word + ' ', endwords from pals p cross join words w where len(p.startchars) len(p.endchars) and (w.word like '%' + reverse(right(startchars,len(startchars)-len(endchars))) or reverse(right(startchars,len(startchars)-len(endchars))) like '%' + w.word) and startwords not like '% ' + w.word + ' %' and endwords not like '% ' + w.word + ' %' ) select rtrim(ltrim(startwords)) + ' ' + rtrim(ltrim(endwords)) from pals where len(startchars) > 0 and startchars + endchars = reverse(startchars + endchars)
Rob's description of the solution:
"I figure that the best way of approaching this would be to build it up,
looking for words that would fit as candidates for being added to the start
or end of my palindromes. I wanted to have a space-separated word list as
well as a spaces-removed word list - one is good for both presentation at
the end and checking for unique words, the other is good for actually making
sure that the palindrome is being built correctly.
So taking the 'build it up' approach, a CTE seemed the way to go. I put a
starting scenario in which was to have an empty string at the start and end.
I was originally planning to remove this entry once the CTE was done, but
then later decisions changed my mind for me.
I figured I had three states that I could find myself in. One was when the
string holding the start of the palindrome was longer than the string
holding the end, another was when the string holding the end was longer than
the start, and the third state was when they were the same length. This
could then form a foundation for building the CTE (which I will come to in
the next paragraph). Once the CTE was built, I could filter out the working
lines - which were those ones where the result wasn't a palindrome, and the
base (empty) entry.
So when one string was longer than the other, I wanted to add a word to the
other side. This word had to be a candidate, so that if the difference
between the start-part and end-part was 'never' in the end-part, I could add
any word to the start-part that matched 'reven%', or was one of 'r', 're',
'rev', 'reve' (which translates into: 'reven' like word + '%'). Similar
logic would apply to the end. If the sides were even, I would have to find a
word for which there was candidate for the other side. So I wouldn't pick
'never' for the end-part if there wasn't a word that I would be able to
populate in the next step. I figured I could probably just throw in any word
here and the algorithm would still be valid (because it would get discarded
as a candidate later), but I included it anyway, thinking that it would be
good to get rid of bad candidates earlier.
Regardless of what state I was in, I also had to make sure I hadn't already
used the word, which is why lines like
startwords not like '% ' + w.word + ' %'
--keep appearing everywhere.
The fact that I wanted to cater for when I had the same length string on
both sides influenced me to leave the base case in there as an empty string.
Otherwise I would need to have a base which queried the words table for
candidate words, and that didn't really appeal to me all that much. And I
wasn't really looking for the fastest way of doing it, I was just looking
for a way of doing it.
And that's about it really... I just built the palindromes from the outside
in, populating a CTE, which I then queried to make sure that I only returned
And here's the solution that I came up with (267 ms):
with c as ( select cast(word as varchar(max)) as st, cast('' as varchar(max)) as ed, 0 as consider from words where word = reverse(word) union all select ' ' + w1.word + ' ', w2.word + ' ', 1 from words as w1 join words as w2 on w1.word w2.word where w1.word like reverse(w2.word) + '%' or reverse(w2.word) like w1.word + '%' union all select st + word + ' ', ed, 0 from c join words on consider = 1 and st + ed not like '% ' + word + ' %' where replace(st + word + ed, ' ', '') = reverse(replace(st + word + ed, ' ', '')) union all select st + w1.word + ' ', w2.word + ' ' + ed, 1 from c join words as w1 on consider = 1 and st + ed not like '% ' + w1.word + ' %' join words as w2 on w1.word w2.word and st + ed not like '% ' + w2.word + ' %' where replace(st, ' ', '') + w1.word like reverse(w2.word + replace(ed, ' ', '')) + '%' or reverse(w2.word + replace(ed, ' ', '')) like replace(st, ' ', '') + w1.word + '%' ) select ltrim(rtrim(st + ed)) as palindrome from c where replace(st + ed, ' ', '') = reverse(replace(st + ed, ' ', ''));
The logic in my solution is similar to the others who did not use the brute
The first CTE query (non recursive) simply isolates the single words that are
The second CTE query (also non recursive) generates two parts of sentences
(start part and end part) out of pairs of words that are either palindromes or
have potential to become palindromes. Start and end pairs have potential to
become a palindrome if start begins with the reverse of end, or the reverse of
end begins with the start.
The third CTE query (recursive) adds a word between start and end
only for words that do not yet appear in the sentence, and make the sentence
The fourth CTE query (recursive) adds a pair of words; one after the start
one before the end, only in cases that become palindromes or have the
potential to become palindromes.