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 approachdef 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 Codeif __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 approachfunction 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 Codelet N = 4, M = 3;let s=["omg", "bbb", "ffd", "gmo"];// Function Callmax_len(s, N, M);// This code is contributed by patel2127</script> |
Output:
omgbbbgmo
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
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!
