Given an array of strings S[] consisting of N distinct strings of length M. The task is to generate the longest possible palindromic string by concatenating some strings from the given array.
Examples:
Input: N = 4, M = 3, S[] = {“omg”, “bbb”, “ffd”, “gmo”}
Output: omgbbbgmo
Explanation: Strings “omg” and “gmo” are reverse of each other and “bbb” is itself a palindrome. Therefore, concatenating “omg” + “bbb” + “gmo” generates the longest palindromic string “omgbbbgmo”.Input: N = 4, M = 3, s[]={“poy”, “fgh”, “hgf”, “yop”}
Output: poyfghhgfyop
Approach: Follow the steps below to solve the problem:
- Initialize a Set and insert each string from the given array in the Set.
- Initialize two vectors left_ans and right_ans to keep track of palindromic strings obtained.
- Now, iterate over the array of strings and check if its reverse exists in the Set or not.
- If found to be true, insert one of the strings into left_ans and the other into right_ans and erase both the strings from the Set to avoid repetition.
- If a string is a palindrome and its pair does not exist in the Set, then that string needs to be appended to the middle of the resultant string.
- Print the resultant string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; void max_len(string s[], int N, int M) { // Stores the distinct strings // from the given array unordered_set<string> set_str; // Insert the strings into set for ( int i = 0; i < N; i++) { set_str.insert(s[i]); } // Stores the left and right // substrings of the given string vector<string> left_ans, right_ans; // Stores the middle substring string mid; // Traverse the array of strings for ( int i = 0; i < N; i++) { string t = s[i]; // Reverse the current string reverse(t.begin(), t.end()); // Checking if the string is // itself a palindrome or not if (t == s[i]) { mid = t; } // Check if the reverse of the // string is present or not else if (set_str.find(t) != set_str.end()) { // Append to the left substring left_ans.push_back(s[i]); // Append to the right substring right_ans.push_back(t); // Erase both the strings // from the set set_str.erase(s[i]); set_str.erase(t); } } // Print the left substring for ( auto x : left_ans) { cout << x; } // Print the middle substring cout << mid; reverse(right_ans.begin(), right_ans.end()); // Print the right substring for ( auto x : right_ans) { cout << x; } } // Driver Code int main() { int N = 4, M = 3; string s[] = { "omg" , "bbb" , "ffd" , "gmo" }; // Function Call max_len(s, N, M); return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ 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); } static void max_len(String s[], int N, int M) { // Stores the distinct Strings // from the given array HashSet<String> set_str = new HashSet<>(); // Insert the Strings // into set for ( int i = 0 ; i < N; i++) { set_str.add(s[i]); } // Stores the left and right // subStrings of the given String Vector<String> left_ans = new Vector<>(); Vector<String> right_ans = new Vector<>(); // Stores the middle // subString String mid = "" ; // Traverse the array // of Strings for ( int i = 0 ; i < N; i++) { String t = s[i]; // Reverse the current // String t = reverse(t); // Checking if the String is // itself a palindrome or not if (t == s[i]) { mid = t; } // Check if the reverse of the // String is present or not else if (set_str.contains(t)) { // Append to the left // subString left_ans.add(s[i]); // Append to the right // subString right_ans.add(t); // Erase both the Strings // from the set set_str.remove(s[i]); set_str.remove(t); } } // Print the left subString for (String x : left_ans) { System.out.print(x); } // Print the middle // subString System.out.print(mid); Collections.reverse(right_ans); // Print the right subString for (String x : right_ans) { System.out.print(x); } } // Driver Code public static void main(String[] args) { int N = 4 , M = 3 ; String s[] = { "omg" , "bbb" , "ffd" , "gmo" }; // Function Call max_len(s, N, M); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach def max_len(s, N, M): # Stores the distinct strings # from the given array set_str = {} # Insert the strings into set for i in s: set_str[i] = 1 # Stores the left and right # substrings of the given string left_ans, right_ans = [], [] # Stores the middle substring mid = "" # Traverse the array of strings for i in range (N): t = s[i] # Reverse the current string t = t[:: - 1 ] # Checking if the is # itself a palindrome or not if (t = = s[i]): mid = t # Check if the reverse of the # is present or not elif (t in set_str): # Append to the left substring left_ans.append(s[i]) # Append to the right substring right_ans.append(t) # Erase both the strings # from the set del set_str[s[i]] del set_str[t] # Print the left substring for x in left_ans: print (x, end = "") # Print the middle substring print (mid, end = "") right_ans = right_ans[:: - 1 ] # Print the right substring for x in right_ans: print (x, end = "") # Driver Code if __name__ = = '__main__' : N = 4 M = 3 s = [ "omg" , "bbb" , "ffd" , "gmo" ] # Function call max_len(s, N, M) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ 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); } static void max_len(String []s, int N, int M) { // Stores the distinct Strings // from the given array HashSet<String> set_str = new HashSet<String>(); // Insert the Strings // into set for ( int i = 0; i < N; i++) { set_str.Add(s[i]); } // Stores the left and right // subStrings of the given String List<String> left_ans = new List<String>(); List<String> right_ans = new List<String>(); // Stores the middle // subString String mid = "" ; // Traverse the array // of Strings for ( int i = 0; i < N; i++) { String t = s[i]; // Reverse the current // String t = reverse(t); // Checking if the String is // itself a palindrome or not if (t == s[i]) { mid = t; } // Check if the reverse of the // String is present or not else if (set_str.Contains(t)) { // Append to the left // subString left_ans.Add(s[i]); // Append to the right // subString right_ans.Add(t); // Erase both the Strings // from the set set_str.Remove(s[i]); set_str.Remove(t); } } // Print the left subString foreach (String x in left_ans) { Console.Write(x); } // Print the middle // subString Console.Write(mid); right_ans.Reverse(); // Print the right subString foreach (String x in right_ans) { Console.Write(x); } } // Driver Code public static void Main(String[] args) { int N = 4, M = 3; String []s = { "omg" , "bbb" , "ffd" , "gmo" }; // Function Call max_len(s, N, M); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the // above approach function reverse(input) { let a = input.split( "" ); a.reverse(); return a.join( "" ); } function max_len(s, N, M) { // Stores the distinct Strings // from the given array let set_str = new Set(); // Insert the Strings // into set for (let i = 0; i < N; i++) { set_str.add(s[i]); } // Stores the left and right // subStrings of the given String let left_ans = []; let right_ans = []; // Stores the middle // subString let mid = "" ; // Traverse the array // of Strings for (let i = 0; i < N; i++) { let t = s[i]; // Reverse the current // String t = reverse(t); // Checking if the String is // itself a palindrome or not if (t == s[i]) { mid = t; } // Check if the reverse of the // String is present or not else if (set_str.has(t)) { // Append to the left // subString left_ans.push(s[i]); // Append to the right // subString right_ans.push(t); // Erase both the Strings // from the set set_str. delete (s[i]); set_str. delete (t); } } // Print the left subString for (let x=0;x< left_ans.length;x++) { document.write(left_ans[x]); } // Print the middle // subString document.write(mid); (right_ans).reverse(); // Print the right subString for (let x = 0; x < right_ans.length; x++) { document.write(right_ans[x]); } } // Driver Code let N = 4, M = 3; let s=[ "omg" , "bbb" , "ffd" , "gmo" ]; // Function Call max_len(s, N, M); // This code is contributed by patel2127 </script> |
Output:
omgbbbgmo
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!