Highest "Valued" Palindrome

Question

So I was at a programming interview a few months ago and this problem tripped me up for some reason. There are a couple of solutions I can think of but most of them seem extremely inefficient. Though I've been programming in some capacity for years, I'm currently in college for a CS degree so my point of reference may be incomplete. I was hoping someone here might offer up some possible solutions:

"Given a set of strings and associated numerical 'values,' assemble a palindrome from these string whose value (defined by the sum of the strings used to create it) is the highest possible."

There were no limits to how many strings could be provided, some strings may not be used.

Example: "asd" - 3 "dsa" - 5 "appa" - 1

Result would be "asdappadsa" with a value of 9.

My thought would be to try all strings in all orders, then drop off one, starting with the lowest valued one, but that solution is O(N!) and I'd assume that's not ok.

(Preferred languages are C and Java, but whatever works)

EDIT: Clarification. Each string provided can only be used once, and has to be used exactly as provided, though you may choose to not use any of the strings in your palindrome. You can not use substrings of provided strings, nor can you reverse the string.

Answer 1

Replace "all strings" with "all palindromes" and the problem space becomes much smaller.

Divide the strings into 26 subsets.

 Strings beginning with x (for 'a' <= x <= 'z')  
   [or whatever the set of "letters" is]

Now divide them into another 26 subsets

 Strings ending with y ( for 'a' <= y <= 'z')

Note each string appears in a "begins with" set and an "ends with" set.

Use these sets to guide creation of all possible palindromes.

 Start with two empty strings:  prefix and suffix
 for each string in the original set
    assign it to the prefix
    call recursiveFunction(prefix, suffix)

 def recursiveFunction(prefix, suffix):
    if prefix + <anything> + suffix cannot form a palindrome return
    if prefix + suffix is a palindrome, remember it
    while you have unused strings
      if the suffix is shorter than the prefix
           Look at the first unmatched character in the prefix
           for each unused string that ends in that character
              call recursiveFunction(prefix, string + suffix)

      else if prefix is shorter than suffix
         look at the last unmatched character in the suffix
            for each unused string that ends with that character
               call recursiveFunction(prefix + string, suffix)
      else // suffix and prefix have equal lenghths
         for each unused string
           call recursiveFunction(prefix + string, suffix)   

Be sure to mark the string used in both begins with and ends when you use it. And be sure to consider the impact of recursion on the "used" marker.

Then pick the palindrome with the best score.