Dada una array de n strings que contienen letras minúsculas. Encuentre el tamaño del subconjunto más grande de strings que son anagramas entre sí. Un anagrama de una string es otra string que contiene los mismos caracteres, solo el orden de los caracteres puede ser diferente. Por ejemplo, «abcd» y «dabc» son anagramas entre sí.
Input:
ant magenta magnate tan gnamate
Output: 3
Explanation
Anagram strings(1) - ant, tan
Anagram strings(2) - magenta, magnate,
gnamate
Thus, only second subset have largest
size i.e., 3
Input:
cars bikes arcs steer
Output: 2
El enfoque ingenuo es generar todo el subconjunto posible e iterar desde el tamaño más grande del subconjunto que contiene todas las strings que tienen el mismo tamaño y anagrama entre sí. La complejidad temporal de este enfoque es O( 
), donde n y m son el tamaño de la array y la longitud de la string, respectivamente.
El enfoque eficiente es usar hashing y sorting. Ordene todos los caracteres de la string y almacene el valor hash (string ordenada) en el mapa ( unordered_map en C++ y HashMap en Java ). Por último, compruebe cuál es la palabra ordenada por frecuencia con el mayor número de ocurrencias.
C++
// C++ Program to find the size of
// largest subset of anagram
#include <bits/stdc++.h>
using namespace std;
// Utility function to find size of
// largest subset of anagram
int largestAnagramSet(string arr[], int n)
{
int maxSize = 0;
unordered_map<string, int> count;
for (int i = 0; i < n; ++i) {
// sort the string
sort(arr[i].begin(), arr[i].end());
// Increment the count of string
count[arr[i]] += 1;
// Compute the maximum size of string
maxSize = max(maxSize, count[arr[i]]);
}
return maxSize;
}
// Driver code
int main()
{
string arr[] = { "ant", "magenta",
"magnate", "tan", "gnamate" };
int n = sizeof(arr) / sizeof(arr[0]);
cout << largestAnagramSet(arr, n) << "\n";
string arr1[] = { "cars", "bikes", "arcs",
"steer" };
n = sizeof(arr1) / sizeof(arr[0]);
cout << largestAnagramSet(arr1, n);
return 0;
}
Java
// Java Program to find the size of
// largest subset of anagram
import java.util.*;
class GFG
{
// Utility function to find size of
// largest subset of anagram
static int largestAnagramSet(String arr[], int n)
{
int maxSize = 0;
HashMap<String, Integer> count = new HashMap<>();
for (int i = 0; i < n; ++i)
{
// sort the String
char temp[] = arr[i].toCharArray();
Arrays.sort(temp);
arr[i] = new String(temp);
// Increment the count of String
if(count.containsKey(arr[i]))
{
count.put(arr[i], count.get(arr[i]) + 1);
}
else
{
count.put(arr[i], 1);
}
// Compute the maximum size of String
maxSize = Math.max(maxSize, count.get(arr[i]));
}
return maxSize;
}
// Driver code
public static void main(String[] args)
{
String arr[] = { "ant", "magenta",
"magnate", "tan", "gnamate" };
int n = arr.length;
System.out.println(largestAnagramSet(arr, n));
String arr1[] = { "cars", "bikes",
"arcs", "steer" };
n = arr1.length;
System.out.println(largestAnagramSet(arr1, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 Program to find the size of
# largest subset of anagram
# Utility function to find size of
# largest subset of anagram
def largestAnagramSet(arr, n) :
maxSize = 0
count = {}
for i in range(n) :
# sort the string
arr[i] = ''.join(sorted(arr[i]))
# Increment the count of string
if arr[i] in count :
count[arr[i]] += 1
else :
count[arr[i]] = 1
# Compute the maximum size of string
maxSize = max(maxSize, count[arr[i]])
return maxSize
# Driver code
arr = [ "ant", "magenta", "magnate", "tan", "gnamate" ]
n = len(arr)
print(largestAnagramSet(arr, n))
arr1 = [ "cars", "bikes", "arcs", "steer" ]
n = len(arr1)
print(largestAnagramSet(arr1, n))
# This code is contributed by divyeshrabadiya072019
C#
// C# Program to find the size of
// largest subset of anagram
using System;
using System.Collections.Generic;
class GFG
{
// Utility function to find size of
// largest subset of anagram
static int largestAnagramSet(String []arr, int n)
{
int maxSize = 0;
Dictionary<String,
int> count = new Dictionary<String,
int>();
for (int i = 0; i < n; ++i)
{
// sort the String
char []temp = arr[i].ToCharArray();
Array.Sort(temp);
arr[i] = new String(temp);
// Increment the count of String
if(count.ContainsKey(arr[i]))
{
count[arr[i]] = count[arr[i]] + 1;
}
else
{
count.Add(arr[i], 1);
}
// Compute the maximum size of String
maxSize = Math.Max(maxSize, count[arr[i]]);
}
return maxSize;
}
// Driver code
public static void Main(String[] args)
{
String []arr = {"ant", "magenta",
"magnate", "tan", "gnamate"};
int n = arr.Length;
Console.WriteLine(largestAnagramSet(arr, n));
String []arr1 = {"cars", "bikes",
"arcs", "steer"};
n = arr1.Length;
Console.WriteLine(largestAnagramSet(arr1, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript Program to find the size of
// largest subset of anagram
// Utility function to find size of
// largest subset of anagram
function largestAnagramSet(arr, n)
{
var maxSize = 0;
var count = new Map();
for(var i = 0; i < n; ++i)
{
// sort the String
var temp = arr[i].split('');
temp.sort();
arr[i] = temp.join('');
// Increment the count of String
if(count.has(arr[i]))
{
count.set(arr[i], count.get(arr[i])+1);
}
else
{
count.set(arr[i], 1);
}
// Compute the maximum size of String
maxSize = Math.max(maxSize, count.get(arr[i]));
}
return maxSize;
}
// Driver code
var arr = ["ant", "magenta",
"magnate", "tan", "gnamate"];
var n = arr.length;
document.write(largestAnagramSet(arr, n) + "<br>");
var arr1 = ["cars", "bikes",
"arcs", "steer"];
n = arr1.length;
document.write(largestAnagramSet(arr1, n));
</script>
Producción:
3 2
Complejidad de tiempo: O( 
) donde m es el tamaño máximo entre todas las strings
Espacio auxiliar: O(n + m)
El mejor enfoque es almacenar la array de frecuencia de cada palabra. En esto, solo necesitamos iterar sobre los caracteres de las palabras e incrementar la frecuencia de la letra actual. Por último, incremente el conteo de solo arreglos de frecuencia idénticos[] y tome el máximo entre ellos. Este enfoque es mejor solo cuando la longitud de las strings es máxima en comparación con el tamaño de la array .
cpp
// C++ Program to find the size of
// largest subset of anagram
#include <bits/stdc++.h>
using namespace std;
// Utility function to find size of
// largest subset of anagram
int largestAnagramSet(string arr[], int n)
{
int maxSize = 0;
// Initialize map<> of vector array
map<vector<int>, int> count;
for (int i = 0; i < n; ++i) {
// Vector array to store
// frequency of element
vector<int> freq(26);
for (char ch : arr[i])
freq[ch - 'a'] += 1;
// Increment the count of
// frequency array in map<>
count[freq] += 1;
// Compute the maximum size
maxSize = max(maxSize, count[freq]);
}
return maxSize;
}
// Driver code
int main()
{
string arr[] = { "ant", "magenta", "magnate",
"tan", "gnamate" };
int n = sizeof(arr) / sizeof(arr[0]);
cout << largestAnagramSet(arr, n) << "\n";
string arr1[] = { "cars", "bikes", "arcs",
"steer" };
n = sizeof(arr1) / sizeof(arr[0]);
cout << largestAnagramSet(arr1, n);
return 0;
}
Python3
# Python Program to find the size of
# largest subset of anagram
# Utility function to find size of
# largest subset of anagram
def largestAnagramSet(arr, n):
maxSize = 0
# Initialize dictionary of array
count = {}
for i in range(n):
# list to store
# frequency of element
freq=[0 for i in range(26)]
for ch in arr[i]:
freq[ord(ch) - ord('a')] += 1
# Increment the count of
# frequency array in dictionary
temp = "".join(str(i) for i in freq)
if temp not in count:
count[temp] = 1
else:
count[temp] += 1
# Compute the maximum size
maxSize = max(maxSize, count[temp])
return maxSize
# Driver code
arr = ["ant", "magenta", "magnate","tan", "gnamate"]
n = len(arr)
print(largestAnagramSet(arr, n))
arr1 = ["cars", "bikes", "arcs", "steer"]
n = len(arr1)
print(largestAnagramSet(arr1, n))
# This code is contributed by rag2127
Javascript
<script>
// JavaScript Program to find the size of
// largest subset of anagram
// Utility function to find size of
// largest subset of anagram
function largestAnagramSet(arr, n){
let maxSize = 0
// Initialize dictionary of array
let count = new Map()
for(let i = 0; i < n; i++){
// list to store
// frequency of element
let freq=new Array(26).fill(0)
for(let ch of arr[i])
freq[ch.charCodeAt(0) - 'a'.charCodeAt(0)] += 1
// Increment the count of
// frequency array in dictionary
let temp = freq.join('')
if(count.has(temp) == false)
count.set(temp,1)
else
count.set(temp, count.get(temp)+ 1)
// Compute the maximum size
maxSize = Math.max(maxSize, count.get(temp))
}
return maxSize
}
// Driver code
let arr = ["ant", "magenta", "magnate","tan", "gnamate"]
let n = arr.length
document.write(largestAnagramSet(arr, n),"</br>")
let arr1 = ["cars", "bikes", "arcs", "steer"]
n = arr1.length
document.write(largestAnagramSet(arr1, n),"</br>")
// This code is contributed by shinjanpatra
</script>
Output 3 2
Complejidad temporal: O( 
) donde m es el tamaño máximo entre todas las strings
Espacio auxiliar: O(n + m)
Publicación traducida automáticamente
Artículo escrito por Shubham Bansal 13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA