### Piyush_Paul_'s blog

By Piyush_Paul_, history, 3 weeks ago,

Hi everyone,

I recently participated in a coding test for a software development role and encountered an intriguing problem. It's an advanced version of the LeetCode question 2131. Longest Palindrome by Concatenating Two Letter Words.

For those unfamiliar with the original question, here's a brief description:

You are given an array of strings words. Each element of words consists of two lowercase English letters. Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

In the advanced version I faced, the constraints are relaxed so that words can be of any length, not just two letters. Here are a couple of examples to illustrate:

words = {"abab", "a"}: The longest palindrome that can be formed is "ababa" with a length of 5. words = {"ab", "aba", "xy"}: The longest palindrome that can be formed is "ababa" with a length of 5. The problem is challenging due to the added complexity of handling words of varying lengths. I would love to hear your thoughts and suggestions on how to approach solving this problem.

constraints:- 0<=words.length<=1000 0<=words[i]<=1000

• +3

 » 3 weeks ago, # |   0 To solve this problem, we need to form the longest palindrome using elements from the words array. Here's a structured approach to achieve this:Steps to Solution: Understanding Palindrome Construction:A palindrome reads the same forwards and backwards. To maximize its length, we can use characters symmetrically around a potential center. Character Frequency Count:Count the frequency of each character (or each element in the case of strings) in the words array. Constructing the Palindrome:For each element in words, add characters in pairs (or even number of times) to ensure they can form a palindrome. If there are any characters left with odd frequencies, we can use one of them as the central character of the palindrome (since a palindrome can have at most one odd-character frequency in its center). Implementation Strategy:Count frequencies of characters (or strings). Accumulate pairs of characters (or strings). If there are characters left with odd frequencies, use one of them in the center of the palindrome. Calculate the length of the palindrome based on the accumulated pairs and the optional center character.
•  » » 3 weeks ago, # ^ |   +5 I hope, that it will be useful for you
•  » » 3 weeks ago, # ^ |   +3 I don't think that will help If I am thinking what you are thinking, can you get me an example to support your answer
•  » » 3 weeks ago, # ^ |   +16 Why does it sound like its written by AI. Also you are telling to take the characters which are even in number from each string in the array and take them in the final answer to from a palindrome with taking atmost 1 odd character which we cannot do in the question asked. We are supposed to concatenate the strings to from a palindrome
•  » » » 3 weeks ago, # ^ |   +3 The question came in the Online assessment conducted by DeShaw recently and adding to the point I never asked to take characters with even frequency from string, it can be and cannot be, eg1[ab, xyz, ba]-> abxyzba, eg2[aa, xy, aa]-> aaaa, eg3[mno, kmp, ababa, pp, qp]-> ababa, hope this might help you
•  » » » » 3 weeks ago, # ^ |   +3 I understood the question but the solution given by Bekbolot_Ubaidullaev is not correct. For instance , ["ab" , "bba" ] has the maximum palindrome length of 5 "abbba" but it will not give 5 as answer. Also in your eg1 , abxyzba is not a palindrome and the answer should be abba .
 » 3 weeks ago, # |   0 I think it came in Salesforce OA recently instead of DE Shaw about which you mentioned in comments of the same blog #include using namespace std; #define ll long long #define MOD 1000000007 int maxConcatenatedPalindrome(vector& words){ unordered_map mp; int len = 0; bool hasOddPalindrome = false; for(string& word : words) mp[word]++; int x = -1; for(auto& pair : mp){ string word = pair.first; int wordCount = pair.second; int n = word.length(); string temp = word; reverse(temp.begin(), temp.end()); if(word == temp){ if(wordCount % 2 == 0){ len += (wordCount * n); } else{ len += (wordCount - 1) * n; x = n; hasOddPalindrome = true; } } else if(mp.find(temp) != mp.end()){ int tempCount = mp[temp]; int pairs = min(wordCount, tempCount); len += pairs * 2 * n; mp[temp] = 0; } } if(hasOddPalindrome) len += x; //middle return len; } int main() { vector words1 = {"y", "xyx", "abc", "cba", "bac", "y", "y"}; vector words2 = {"y", "xyx", "abc", "cba", "bac", "y"}; vector words3 = {"ab", "ba", "xyx", "de"}; vector words4 = {"xy", "abc", "xyx", "bac", "cab", "cba"}; cout << maxConcatenatedPalindrome(words1) << "\n"; cout << maxConcatenatedPalindrome(words2) << "\n"; cout << maxConcatenatedPalindrome(words3) << "\n"; cout << maxConcatenatedPalindrome(words4) << "\n"; return 0; } 
•  » » 3 weeks ago, # ^ |   +1 {"abcd", "edc", "ba", "xyz", "pqr"} fails here-> abcd-edc-ba
•  » » 2 weeks ago, # ^ |   0 deserving unrated
•  » » 2 weeks ago, # ^ |   0 try test cases before posting
 » 3 weeks ago, # |   0 Have anyone got the solution?
•  » » 2 weeks ago, # ^ |   0 Probably the company will give bonus since it is an np hard problem
•  » » » 2 weeks ago, # ^ |   0 lol