## Question:

**Astro and bunch of words**

Astro is getting bored and want to play some interesting game. He noticed some random words written on a page of a book, and now he is wondering the maximum length of a palindrome that can be formed by concatenating any number of words.

Can you please help Astro?

Please complete the function maxConcatenated Palindrome which takes following input:

words = List of strings

**Returns**

Integer denoting maximum length of a palindrome that can be formed by concatenating any number of words and if no palindrome can be formed, return 0.

**Constraints**

• The length of each string in `words[]`

is at most 1000 characters.

• The number of strings in `words []`

is at most 1000.

• The total length of all strings in `words []`

does not exceed 10^6 characters.

• Each string in `words[]`

can be used at most once.

**Example Input**

`[]words = {"ab", "ba", "xyx", "de"};`

**Output**

7

## My Approach:

The only approach I could think of was bruteforce (checking all possible strings if they are palindrome) . How to solve it efficiently?

1 Like

one approach that i am able to think of that is combine all the strings of array to a single string and count no. of those letters which have frequency greater than equal to two as they can be used both side to forming a palindrome then after using all of them if u are left with more than one element than answer will be count of all letters used +1. dont know if this will work.

1 Like

Could you please explain a bit more about how to approach this problem using a trie?

That won’t work, as we have to take one string at a time. We can’t break a string into characters.

Do you have all the Questions asked in Salesforce OA

What is the intuition behind it?

Longest palindrome will depend on the permutation of strings which we’re taking, so how will this work on taking any random permutation of strings in s?

Like in case of ab cd ef dc fe kg, answer should be 8(cdeffedc), but(correct me if I’m wrong) on taking s=abcdefdcfekg, ans1=4, ans2=8, so as per your statement, it should be 4.

Like in case of ab cd ef dc fe kg, answer should be 8(cdeffedc), but(correct me if I’m wrong) on taking s=abcdefdcfekg, ans1=4, ans2=8, so as per your statement, it should be 4.

Yes you are right even if we concatenate the string |N| times that will give us answer but that would be trying out all possible ways… so my bad ig.