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.