Subsecuencia de anagrama común más larga de N strings

Dadas N strings. Encuentre la subsecuencia más larga posible de cada una de estas N strings de modo que sean anagramas entre sí. La tarea es imprimir la subsecuencia lexicográficamente más grande entre todas las subsecuencias. 

Ejemplos: 

Entrada: s[] = { geeks, esrka, efrsk } 
Salida: ske  La
primera string tiene «eks», la segunda string tiene «esk», la tercera string tiene «esk». Estos tres son anagramas. “ske” es lexicográficamente grande. 

Entrada: string s[] = { loop, lol, oliva } 
Salida: ol

Acercarse :  

• Cree una array bidimensional de n*26 para almacenar la frecuencia de cada carácter en la string.
• Después de hacer una array de frecuencias, recorra en dirección inversa para cada dígito y encuentre la string que tiene el mínimo de caracteres de este tipo.
• Después de completar el recorrido inverso, imprima el carácter que ocurre el número mínimo de veces ya que da la string lexicográficamente más grande.

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

// C++ program to find longest possible
// subsequence anagram of N strings.
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
 
// function to store frequency of
// each character in each string
void frequency(int fre[][MAX_CHAR], string s[], int n)
{
    for (int i = 0; i < n; i++) {
        string str = s[i];
        for (int j = 0; j < str.size(); j++)
            fre[i][str[j] - 'a']++;       
    }
}
 
// function to Find longest possible sequence of N
// strings which is anagram to each other
void LongestSequence(int fre[][MAX_CHAR], int n)
{
    // to get lexicographical largest sequence.
    for (int i = MAX_CHAR-1; i >= 0; i--) {
 
        // find minimum of that character
        int mi = fre[0][i];
        for (int j = 1; j < n; j++)
            mi = min(fre[j][i], mi);       
 
        // print that character
        // minimum number of times
        while (mi--)
            cout << (char)('a' + i);       
    }
}
 
// Driver code
int main()
{
 
    string s[] = { "loo", "lol", "olive" };
    int n = sizeof(s)/sizeof(s[0]);
 
    // to store frequency of each character in each string
    int fre[n][26] = { 0 };
 
    // to get frequency of each character
    frequency(fre, s, n);
 
    // function call
    LongestSequence(fre, n);
 
    return 0;
}

// Java program to find longest
// possible subsequence anagram
// of N strings.
class GFG
{
final int MAX_CHAR = 26;
 
// function to store frequency
// of each character in each
// string
static void frequency(int fre[][],
                      String s[], int n)
{
    for (int i = 0; i < n; i++)
    {
        String str = s[i];
        for (int j = 0;
                 j < str.length(); j++)
            fre[i][str.charAt(j) - 'a']++;    
    }
}
 
// function to Find longest
// possible sequence of N
// strings which is anagram
// to each other
static void LongestSequence(int fre[][],
                            int n)
{
    // to get lexicographical
    // largest sequence.
    for (int i = 25; i >= 0; i--)
    {
 
        // find minimum of
        // that character
        int mi = fre[0][i];
        for (int j = 1; j < n; j++)
            mi = Math.min(fre[j][i], mi);    
 
        // print that character
        // minimum number of times
        while (mi--!=0)
            System.out.print((char)('a' + i));    
    }
}
 
// Driver code
public static void main(String args[])
{
 
    String s[] = { "loo", "lol", "olive" };
    int n = s.length;
 
    // to store frequency of each
    // character in each string
    int fre[][] = new int[n][26] ;
 
    // to get frequency
    // of each character
    frequency(fre, s, n);
 
    // function call
    LongestSequence(fre, n);
}
}
 
// This code is contributed
// by Arnab Kundu

# Python3 program to find longest possible
# subsequence anagram of N strings.
 
# Function to store frequency of
# each character in each string
def frequency(fre, s, n):
 
    for i in range(0, n):
        string = s[i]
        for j in range(0, len(string)):
            fre[i][ord(string[j]) - ord('a')] += 1       
 
# Function to Find longest possible sequence 
# of N strings which is anagram to each other
def LongestSequence(fre, n):
 
    # to get lexicographical largest sequence.
    for i in range(MAX_CHAR-1, -1, -1):
 
        # find minimum of that character
        mi = fre[0][i]
        for j in range(1, n):
            mi = min(fre[j][i], mi)        
 
        # print that character
        # minimum number of times
        while mi:
            print(chr(ord('a') + i), end = "")
            mi -= 1
     
# Driver code
if __name__ == "__main__":
 
    s = ["loo", "lol", "olive"]
    n = len(s)
    MAX_CHAR = 26
 
    # to store frequency of each
    # character in each string
    fre = [[0 for i in range(26)]
              for j in range(n)]
 
    # To get frequency of each character
    frequency(fre, s, n)
 
    # Function call
    LongestSequence(fre, n)
 
# This code is contributed by
# Rituraj Jain

// c# program to find longest
// possible subsequence anagram
// of N strings.
using System;
 
class GFG
{
public readonly int MAX_CHAR = 26;
 
// function to store frequency
// of each character in each
// string
public static void frequency(int[,] fre,
                             string[] s, int n)
{
    for (int i = 0; i < n; i++)
    {
        string str = s[i];
        for (int j = 0;
                 j < str.Length; j++)
        {
            fre[i, str[j] - 'a']++;
        }
    }
}
 
// function to Find longest
// possible sequence of N
// strings which is anagram
// to each other
public static void LongestSequence(int[, ] fre,
                                   int n)
{
    // to get lexicographical
    // largest sequence.
    for (int i = 24; i >= 0; i--)
    {
 
        // find minimum of
        // that character
        int mi = fre[0, i];
        for (int j = 1; j < n; j++)
        {
            mi = Math.Min(fre[j, i], mi);
        }
 
        // print that character
        // minimum number of times
        while (mi--!=0)
        {
            Console.Write((char)('a' + i));
        }
    }
}
 
// Driver code
public static void Main(string[] args)
{
 
    string[] s = new string[] {"loo", "lol", "olive"};
    int n = s.Length;
 
    // to store frequency of each
    // character in each string
    int[, ] fre = new int[n, 26];
 
    // to get frequency
    // of each character
    frequency(fre, s, n);
 
    // function call
    LongestSequence(fre, n);
}
}
 
// This code is contributed by Shrikanth13

<script>
 
// JavaScript program to find longest
// possible subsequence anagram
// of N strings.
 
let MAX_CHAR = 26;
 
// function to store frequency
// of each character in each
// string
function frequency(fre,s,n)
{
    for (let i = 0; i < n; i++)
    {
        let str = s[i];
        for (let j = 0;
                 j < str.length; j++)
            fre[i][str[j].charCodeAt(0) - 'a'.charCodeAt(0)]++;   
    }
}
 
// function to Find longest
// possible sequence of N
// strings which is anagram
// to each other
function LongestSequence(fre,n)
{
    // to get lexicographical
    // largest sequence.
    for (let i = 24; i >= 0; i--)
    {
  
        // find minimum of
        // that character
        let mi = fre[0][i];
        for (let j = 1; j < n; j++)
            mi = Math.min(fre[j][i], mi);   
  
        // print that character
        // minimum number of times
        while (mi--!=0)
            document.write(String.fromCharCode
            ('a'.charCodeAt(0) + i));   
    }
}
 
// Driver code
let s=["loo", "lol", "olive"];
let n = s.length;
  
// to store frequency of each
// character in each string
let fre = new Array(n) ;
for(let i=0;i<n;i++)
{
    fre[i]=new Array(26);
    for(let j=0;j<26;j++)
        fre[i][j]=0;
}
 
// to get frequency
// of each character
frequency(fre, s, n);
 
// function call
LongestSequence(fre, n);
 
// This code is contributed by avanitrachhadiya2155
 
</script>

ol

Complejidad temporal: O(n ² )

Espacio auxiliar: O(1). 

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.