Given an array arr[] consisting of N strings of equal length M, the task is to create the longest palindrome by concatenating the strings. Reordering and discarding some strings from the given set of strings can also be done.
Examples:
Input: N = 3, arr[] = { “tab”, “one”, “bat” }, M = 3
Output: tabbat
Explanation:
On combining “tab” and “bat” from the given set of input strings, the longest palindromic string is formed.
Input: N = 4, arr[] = { “oo”, “ox”, “xo”, “xx” }, M = 2
Output: oxxxxo
Observation: Let us assume that we chose some K strings from the given array and the string which we get after choosing those K strings is a palindrome. Then the observation which needs to be made for the possible K values are:
- K is even: Then for every integer x (1 <= x <= K/2):
Sx = rev(SK - x + 1)
- For example, if the strings which form the longest palindrome are S1 = “tab”, S2 = “ab”, S3 = “ba”, S4 = “bat”. Here, K = 4. Therefore, S1 = rev(S4) and S2 = rev(S3).
- K is odd: Apart from the above observation, the middle string S(K+1)/2 is a palindrome.
Approach: Clearly, from the above observation, to get the largest palindrome, the given array must also contain the reverse of the string. Therefore, for every string, we find if there is another string that is its reverse. If there exists, then we add this pair of strings to the left and right end respectively. If there are one or more strings that are palindrome themselves, pick any one of them and put it in the middle.
Below is the implementation of the above approach:
C++
// C++ program to find the// Longest palindrome that can be formed// by concatenating and reordering// given N strings of equal length#include <bits/stdc++.h>using namespace std;// Function to print the longest palindromevoid printPalindrome(vector<string> left, string mid, vector<string> right){ // Printing every string in left vector for (string x : left) cout << x; // Printing the palindromic string // in the middle cout << mid; // Printing the reverse of the right vector // to make the final output palindromic reverse(right.begin(), right.end()); for (string x : right) cout << x; cout << endl;}// Function to find and print the// longest palindrome that can be formedvoid findPalindrome(vector<string>& S, int N, int M){ set<string> dict; for (int i = 0; i < M; i++) { cin >> S[i]; // Inserting each string in the set dict.insert(S[i]); } // Vectors to add the strings // in the left and right side vector<string> left, right; // To add the already present palindrome // string in the middle of the solution string mid; // Iterating through all the given strings for (int i = 0; i < N; i++) { string t = S[i]; reverse(t.begin(), t.end()); // If the string is a palindrome // it is added in the middle if (t == S[i]) mid = t; // Checking if the reverse // of the string is already // present in the set else if (dict.find(t) != dict.end()) { left.push_back(S[i]); right.push_back(t); dict.erase(S[i]); dict.erase(t); } } printPalindrome(left, mid, right);}// Driver codeint main(){ vector<string> S{ "tab", "one", "bat" }; int M = 3; int N = S.size(); findPalindrome(S, N, M);} |
Java
// Java program to find the// Longest palindrome that can be formed// by concatenating and reordering// given N Strings of equal lengthimport java.util.*;class GFG{ // Function to print the longest palindromestatic void printPalindrome(Vector<String> left, String mid, Vector<String> right){ // Printing every String in left vector for (String x : left) System.out.print(x); // Printing the palindromic String // in the middle System.out.print(mid); // Printing the reverse of the right vector // to make the final output palindromic Collections.reverse(right); for (String x : right) System.out.print(x); System.out.println();} // Function to find and print the// longest palindrome that can be formedstatic void findPalindrome(Vector<String> S, int N, int M){ HashSet<String> dict = new HashSet<String>(); for (int i = 0; i < M; i++) { // Inserting each String in the set dict.add(S.get(i)); } // Vectors to add the Strings // in the left and right side Vector<String> left = new Vector<String>(), right = new Vector<String>(); // To add the already present palindrome // String in the middle of the solution String mid=""; // Iterating through all the given Strings for (int i = 0; i < N; i++) { String t = S.get(i); t = reverse(t); // If the String is a palindrome // it is added in the middle if (t == S.get(i)) mid = t; // Checking if the reverse // of the String is already // present in the set else if (dict.contains(t)) { left.add(S.get(i)); right.add(t); dict.remove(S.get(i)); dict.remove(t); } } printPalindrome(left, mid, right);}static String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);} // Driver codepublic static void main(String[] args){ String arr[] = { "tab", "one", "bat" }; Vector<String> S = new Vector<String>(Arrays.asList(arr)); int M = 3; int N = S.size(); findPalindrome(S, N, M);}}// This code contributed by PrinciRaj1992 |
Python3
# Function to print the longest palindromedef printPalindrome(left,mid,right): # Printing every string in left vector for x in left: print(x, end="") # Printing the palindromic string # in the middle print(mid, end="") # Printing the reverse of the right vector # to make the final output palindromic right = right[::-1] for x in right: print(x, end = "") print('\n', end = "")# Function to find and print the# longest palindrome that can be formeddef findPalindrome(S, N, M): d = set() for i in range(M): # Inserting each string in the set d.add(S[i]) # Vectors to add the strings # in the left and right side left = [] right = [] # To add the already present palindrome # string in the middle of the solution mid = "" # Iterating through all the given strings for i in range(N): t = S[i] t = t[::-1] # If the string is a palindrome # it is added in the middle if (t == S[i]): mid = t # Checking if the reverse # of the string is already # present in the set elif (t in d): left.append(S[i]) right.append(t) d.remove(S[i]) d.remove(t) printPalindrome(left, mid, right)# Driver codeif __name__ == '__main__': S = ["tab", "one", "bat"] M = 3 N = len(S) findPalindrome(S, N, M)# This code is contributed by Surendra_Gangwar |
C#
// C# program to find the// longest palindrome that can be formed// by concatenating and reordering// given N Strings of equal lengthusing System;using System.Collections.Generic;class GFG{// Function to print the longest palindromestatic void printPalindrome(List<String> left, String mid, List<String> right){ // Printing every String in left vector foreach (String x in left) Console.Write(x); // Printing the palindromic String // in the middle Console.Write(mid); // Printing the reverse of the right vector // to make the readonly output palindromic right.Reverse(); foreach (String x in right) Console.Write(x); Console.WriteLine();}// Function to find and print the// longest palindrome that can be formedstatic void findPalindrome(List<String> S, int N, int M){ HashSet<String> dict = new HashSet<String>(); for (int i = 0; i < M; i++) { // Inserting each String in the set dict.Add(S[i]); } // Lists to add the Strings // in the left and right side List<String> left = new List<String>(), right = new List<String>(); // To add the already present palindrome // String in the middle of the solution String mid=""; // Iterating through all the given Strings for (int i = 0; i < N; i++) { String t = S[i]; t = reverse(t); // If the String is a palindrome // it is added in the middle if (t == S[i]) mid = t; // Checking if the reverse // of the String is already // present in the set else if (dict.Contains(t)) { left.Add(S[i]); right.Add(t); dict.Remove(S[i]); dict.Remove(t); } } printPalindrome(left, mid, right);}static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("",a);} // Driver codepublic static void Main(String[] args){ String []arr = { "tab", "one", "bat" }; List<String> S = new List<String>(arr); int M = 3; int N = S.Count; findPalindrome(S, N, M);}}// This code is contributed by Princi Singh |
Javascript
<script>// Function to print the longest palindromefunction printPalindrome(left,mid,right){ // Printing every string in left vector for(let x of left) document.write(x,"") // Printing the palindromic string // in the middle document.write(mid,"") // Printing the reverse of the right vector // to make the final output palindromic right = right.reverse() for(let x of right){ document.write(x,"") } document.write("</br>","")}// Function to find and print the// longest palindrome that can be formedfunction findPalindrome(S, N, M){ let d = new Set() for(let i=0;i<M;i++) // Inserting each string in the set d.add(S[i]) // Vectors to add the strings // in the left and right side let left = [] let right = [] // To add the already present palindrome // string in the middle of the solution let mid = "" // Iterating through all the given strings for(let i=0;i<N;i++){ let t = S[i] t = t.split("").reverse().join("") // If the string is a palindrome // it is added in the middle if (t == S[i]) mid = t // Checking if the reverse // of the string is already // present in the set else if(d.has(t)){ left.push(S[i]) right.push(t) d.delete(S[i]) d.delete(t) } } printPalindrome(left, mid, right)}// Driver codelet S = ["tab", "one", "bat"]let M = 3let N = S.lengthfindPalindrome(S, N, M)// This code is contributed by shinjanpatra</script> |
Output:
tabbat
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
