Longest palindromic string possible by concatenating strings from a given array

0 0 6 minutes read

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)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!