Pair up strings to form palindromes

Question

Given N strings each of at max 1000 length. We can concatenate pair of strings by ends. Like if one is "abc" and other is "cba" then we can get "abccba" as well as "cbaabc". Some string may be left without concatenation to any other string. Also no string can be concatenated to itself.

We can only concatenate those two strings that form a palindrome. So I need to tell the minimum number of strings left after making such pairs.

Example : Let we have 9 strings :

aabbaabb 
bbaabbaa
aa
bb
a
bbaa
bba
bab
ab

Then here answer is 5

Explanation : Here are 5 strings :

"aabbaabb" + "bbaabbaa" = "aabbaabbbbaabbaa"
"aa" + "a = "aaa"
"bba" + "bb" = "bbabb"
"bab" + "ab" = "babab"
"bbaa"

Also there can be 1000 such strings in total.

Answer 1

1) Make a graph where we have one node for each word.

2) Go through all pairs of words and check if they form palindrome if we concatenate them. If they do connect corresponding nodes in graph with edge.

3) Now use matching algorithm to find maximum number of edges you can match: http://en.wikipedia.org/wiki/Blossom_algorithm

Time complexity: O(N) for point 1, O(n*n*1000) for point 2 and O(V^4) for point 3 yielding total complexity of O(n^4).