La string palindrómica más larga posible al concatenar strings de una array dada

Dada una array de strings S[] que consta de N strings distintas de longitud M . La tarea es generar la string palindrómica más larga posible concatenando algunas strings de la array dada.

Ejemplos:

Entrada: N = 4, M = 3, S[] = {“omg”, “bbb”, “ffd”, “gmo”}
Salida: omgbbbgmo
Explicación: Las strings “omg” y “gmo” son inversas entre sí y “bbb” es en sí mismo un palíndromo. Por lo tanto, concatenar “omg” + “bbb” + “gmo” genera la string palindrómica más larga “omgbbbgmo”.

Entrada: N = 4, M = 3, s[]={“poy”, “fgh”, “hgf”, “yop”}
Salida: poyfghhgfyop

Enfoque: siga los pasos a continuación para resolver el problema:

• Inicialice un Set e inserte cada string de la array dada en el Set .
• Inicialice dos vectores left_ans y right_ans para realizar un seguimiento de las strings palindrómicas obtenidas.
• Ahora, itere sobre la array de strings y verifique si su reverso existe en el Conjunto o no.
• Si se determina que es cierto, inserte una de las strings en left_ans y la otra en right_ans y borre ambas strings del Conjunto para evitar repeticiones.
• Si una string es un palíndromo y su par no existe en el Conjunto , entonces esa string debe agregarse a la mitad de la string resultante.
• Imprime la string resultante.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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

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

Producción:

omgbbbgmo

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)