Dadas 2 arrays de strings X e Y , la tarea es encontrar el número de superstrings en X.
Se dice que una string s es una Superstring, si cada string presente en el arreglo Y es una subsecuencia de la string s .
Ejemplos:
Entrada : X = {“ceo”, “alco”, “caaeio”, “ceai”}, Y = {“ec”, “oc”, “ceo”}
Salida : 2
Explicación : Strings “ceo” y “caaeio” son superstrings ya que cada string de la array Y es un subconjunto de estas 2 strings. No se incluyen otras strings en la respuesta; todas las strings de la array Y no son
subconjuntos de ellas.Entrada : X = {“iopo”, “oaai”, “iipo”}, Y = {“oo”}
Salida : 1
Enfoque: La idea es usar el concepto de Hashing para almacenar las frecuencias de los caracteres para resolver el problema. Siga los pasos a continuación para resolver el problema:
- Inicialice una array de tamaño 26 para almacenar el máximo de ocurrencias de cada carácter[az] en cada string presente en la array Y .
- Ahora considere cada string s en X,
- Compruebe si la frecuencia de cada carácter en s es mayor que igual a la frecuencia obtenida del paso anterior
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <iostream>
using namespace std;
// Function to find total number of superstrings
int superstring(string X[], string Y[], int N, int M)
{
// Array to store max frequency
// Of each letter
int maxFreq[26];
for (int i = 0; i < 26; i++)
maxFreq[i] = 0;
for (int j = 0; j < M; j++) {
int temp[26];
for (int i = 0; i < 26; i++)
temp[i] = 0;
for (int k = 0; k < Y[j].size(); k++) {
temp[Y[j][k] - 'a']++;
}
for (int i = 0; i < 26; i++) {
maxFreq[i] = max(maxFreq[i], temp[i]);
}
}
int ans = 0;
for (int j = 0; j < N; j++) {
// Array to find frequency of each letter in string
// x
int temp[26];
for (int i = 0; i < 26; i++)
temp[i] = 0;
for (int k = 0; k < X[j].size(); k++) {
temp[X[j][k] - 'a']++;
}
int i = 0;
for (i = 0; i < 26; i++) {
// If any frequency is less in string x than
// maxFreq, then it can't be a superstring
if (temp[i] < maxFreq[i]) {
break;
}
}
if (i == 26) {
// Increment counter of x is a superstring
ans++;
}
}
return ans;
}
// Driver code
int main()
{
// Size of array X
int N = 4;
// Size of array Y
int M = 3;
string X[N] = { "ceo", "alco", "caaeio", "ceai" };
string Y[M] = { "ec", "oc", "ceo" };
cout << superstring(X, Y, N, M); // Function call
return 0;
}
Java
// Java implementation for the above approach
import java.io.*;
class GFG {
// Function to find total number of superstrings
public static int superString(String X[], String Y[],
int N, int M)
{
// Array to store max frequency
// Of each letter
int[] maxFreq = new int[26];
for (int i = 0; i < 26; i++)
maxFreq[i] = 0;
for (int j = 0; j < M; j++) {
int[] temp = new int[26];
for (int k = 0; k < Y[j].length(); k++) {
temp[Y[j].charAt(k) - 'a']++;
}
for (int i = 0; i < 26; i++) {
maxFreq[i] = Math.max(maxFreq[i], temp[i]);
}
}
int ans = 0;
for (int j = 0; j < N; j++) {
// Array to find frequency of each letter in
// string x
int[] temp = new int[26];
for (int i = 0; i < 26; i++)
temp[i] = 0;
for (int k = 0; k < X[j].length(); k++) {
temp[X[j].charAt(k) - 'a']++;
}
int i = 0;
for (i = 0; i < 26; i++) {
// If any frequency is less in string x than
// maxFreq, then it can't be a superstring
if (temp[i] < maxFreq[i]) {
break;
}
}
if (i == 26) {
// Increment counter of x is a superstring
ans++;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
String[] X = new String[] { "ceo", "alco", "caaeio",
"ceai" };
String[] Y = new String[] { "ec", "oc", "ceo" };
System.out.println(
superString(X, Y, X.length, Y.length));
}
}
Python3
# Python3 implementation for the above approach
# Function to find total number of superstrings
def superstring(X, Y, N, M):
# Array to store max frequency
# Of each letter
maxFreq = [0] * 26
for j in range(M):
temp = [0] * 26
for k in range(len(Y[j])):
temp[ord(Y[j][k]) - ord('a')] += 1
for i in range(26):
maxFreq[i] = max(maxFreq[i], temp[i])
ans = 0
for j in range(N):
# Array to find frequency of each letter
# in string x
temp = [0] * 26
for k in range(len(X[j])):
temp[ord(X[j][k]) - ord('a')] += 1
i = 0
while i < 26:
# If any frequency is less in x than
# maxFreq, then it can't be a superstring
if (temp[i] < maxFreq[i]):
break
i += 1
if (i == 26):
# Increment counter of x is a superstring
ans += 1
return ans
# Driver code
if __name__ == '__main__':
# Size of array X
N = 4
# Size of array Y
M = 3
X = ["ceo", "alco", "caaeio", "ceai"]
Y = [ "ec", "oc", "ceo" ]
print(superstring(X, Y, N, M)) #Function call
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find total number of superstrings
public static int superString(string[] X, string[] Y,
int N, int M)
{
// Array to store max frequency
// Of each letter
int[] maxFreq = new int[26];
for (int i = 0; i < 26; i++)
maxFreq[i] = 0;
for (int j = 0; j < M; j++) {
int[] temp = new int[26];
for (int k = 0; k < Y[j].Length; k++) {
temp[Y[j][k] - 'a']++;
}
for (int i = 0; i < 26; i++) {
maxFreq[i] = Math.Max(maxFreq[i], temp[i]);
}
}
int ans = 0;
for (int j = 0; j < N; j++) {
// Array to find frequency of each letter in
// string x
int[] temp = new int[26];
int i =0;
for ( i = 0; i < 26; i++)
temp[i] = 0;
for (int k = 0; k < X[j].Length; k++) {
temp[X[j][k] - 'a']++;
}
for ( i = 0; i < 26; i++) {
// If any frequency is less in string x than
// maxFreq, then it can't be a superstring
if (temp[i] < maxFreq[i]) {
break;
}
}
if ( i == 26) {
// Increment counter of x is a superstring
ans++;
}
}
return ans;
}
// Driver code
static void Main()
{
string[] X = new String[] { "ceo", "alco", "caaeio",
"ceai" };
string[] Y = new String[] { "ec", "oc", "ceo" };
Console.Write(
superString(X, Y, X.Length, Y.Length));
}
}
// This code is contributed b sanjoy_62.
Javascript
<script>
// JavaScript program for the above approach
// Function to find total number of superstrings
function superString(X, Y, N, M)
{
// Array to store max frequency
// Of each letter
let maxFreq = Array.from({length: 26}, (_, i) => 0);
for (let i = 0; i < 26; i++)
maxFreq[i] = 0;
for (let j = 0; j < M; j++) {
let temp = Array.from({length: 26}, (_, i) => 0);
for (let k = 0; k < Y[j].length; k++) {
temp[Y[j][k].charCodeAt() - 'a'.charCodeAt()]++;
}
for (let i = 0; i < 26; i++) {
maxFreq[i] = Math.max(maxFreq[i], temp[i]);
}
}
let ans = 0;
for (let j = 0; j < N; j++) {
// Array to find frequency of each letter in
// string x
let temp = Array.from({length: 26}, (_, i) => 0);
for (let i = 0; i < 26; i++)
temp[i] = 0;
for (let k = 0; k < X[j].length; k++) {
temp[X[j][k].charCodeAt() - 'a'.charCodeAt()]++;
}
let i = 0;
for (i = 0; i < 26; i++) {
// If any frequency is less in string x than
// maxFreq, then it can't be a superstring
if (temp[i] < maxFreq[i]) {
break;
}
}
if (i == 26) {
// Increment counter of x is a superstring
ans++;
}
}
return ans;
}
// Driver Code
let X = [ "ceo", "alco", "caaeio",
"ceai" ];
let Y = [ "ec", "oc", "ceo" ];
document.write(
superString(X, Y, X.length, Y.length));
</script>
Producción:
2
Complejidad del tiempo: O(N*N1 + M*M1), donde N = tamaño de la array X, N1 = longitud máxima (x), M = tamaño de la array Y, M1 = longitud máxima (y),
Complejidad del espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA