Longest palindromic String formed using concatenation of given strings in any order

Given an array of strings arr[] of the same length, the task is to find the longest palindromic string that can be made using the concatenation of strings in any order. 

Examples:

Input: arr[] = {“aba”, “aba”} 
Output: abaaba

Input: arr[] = {“abc”, “dba”, “kop”, “cba”, “abd”} 
Output: abcdbaabdcba 
 

Approach:  

• Find all the pairs of strings which are reverse of each other and store them in two different arrays pair1[] and pair2 separately and delete those pairs from the original array.
• Find any palindromic string s1 in the array.
• Join all the strings together of the array pair1[] into s2
• Join all the strings together of the array pair2[] in reverse order into s3
• Concatenate the strings s2 + s1 + s3 together to get longest palindromic string.

Below is the implementation of the above approach.

abaaba
abcdbaabdcba

Time Complexity: O(N²)

Auxiliary Space: O(N)

Method 2

Approach: One point to note down is that basically there are two types of strings. First, the strings which are palindrome let us say pallString and second, the strings that are not palindrome let us say notPallString. We will store pallString in a hashmap pallMap and notPallString in hashmap notPallMap. Now assume we have an array ans[] which stores the final palindromic string inside it. We also have two pointers i and j such that i points to starting index of ans and j points to the last index of ans.

Now we will travel our given array, arr. If we get pallString then we will increase its frequency in pallMap. If we get notPallString then it is an interesting case. We will check if it’s reverse, reverse_notPallString exists in notPallMap or not. If reverse_notPallString exists in the notPallMap in that case notPallString and reverse_notpallString can be part of our ans array. So we will add notPallString at index i and reverse_notPallString at index j . We will also decrease the frequency of reverse_notPallString from our notPallMap.  After this, we will increase i and decrease j. If reverse_notpallString does not exist in notPallMap, then we will increase the frequency of notPallString in notPallMap. Similarly, we will travel the whole array. After traveling the whole arr, pallMap will store the strings and their frequency which are palindromes on their own. So we will iterate over the pallMap. Assume we have the string pall_string  and its frequency as freq as we are iterating the pallMap. Now while the freq > 1, we will add pall_string at index i and index j respectively, and will decrease the freq by 2. We will also increase i pointer and decrease j pointer. We will also maintain whether we got any odd freq or not because such pall_string does not require any other string to be part of ans array. So such pall can be at the center of our ans array .

After the above steps, our ans array will store the palindromic arrangements of arr.

Algorithm:

1) Maintain an array ans which will sore the palindromic strings. Pointer i will point to the starting of ans and j will point to the ending of ans

1) Iterate the array arr

2) If you got a pallString, then increase its frequency in the pallMap

3) If you got a notPallString, than

   3.1) Check if its reverse reverse_notPallString exists in the notPallMap or not

  3.2) If the reverse_notPallString exists in notPallMap then add noPallString at index i and                   reverse_notPallString at index j. Also decrease the frequency of reverse_notPallString                 from notPallMap. Increase i pointer and decrease j pointer after the addition of the                  strings in ans .

   3.3) If the reverse_notPallString does not exist in notPallMap then increase the frequency of             notPallString in notPallMap

4) After traveling the arr, travel the pallMap as it will have palindromic strings pall_string with its frequency as freq

5) Now, while the freq > 1, add pall_string at index i and j. Also, decrease the freq by 2.

6) Note if any freq is odd or not because such pall_string, let us say centre_string can be at the center of our array arr as it is a palindrome and does not require any reverse to contribute to the ans .

7) Travel ans and, and store the valid strings in your result (skipping null values)

Below is the implementation of the above approach.

abaaba
abdcbaabcdba

Time Complexity : O(n)

Auxiliary Space : O(n)