Suma de frecuencias de caracteres de una string presentes en otra string

Dadas dos strings S1 y S2 de longitudes M y N respectivamente, la tarea es calcular la suma de las frecuencias de los caracteres de la string S1 en la string S2 .

Ejemplos:

Entrada: S1 = “pPKf”, S2 = “KKKttsdppfP”
Salida: 7
Explicación:
El carácter ‘p’ aparece dos veces en la string S2.
El carácter ‘P’ aparece una vez en la string S2.
El carácter ‘K’ aparece tres veces en la string S2.
El carácter ‘f’ aparece una vez en la string S2.
Por lo tanto, en total, los caracteres de la string S1 aparecen 7 veces en la string S2.

Entrada: S1 = “geEksFOR”, S2 = “GeEksforgeEKS”
Salida: 7

Enfoque ingenuo: el enfoque más simple es iterar sobre cada carácter de la string S1 , contar su frecuencia en la string S2 . 

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de Hashing . Siga los pasos a continuación para resolver el problema:

• Inicialice un conteo de enteros para almacenar la suma requerida.
• Inserte todos los caracteres de la string S1 en un Conjunto , digamos bset .
• Itere sobre los caracteres de la string S2 y verifique si el carácter actual está presente en el conjunto, bset o no. Si se encuentra que es cierto, entonces incremente el conteo en uno.
• Después de completar los pasos anteriores, imprima el valor de conteo como resultado.

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

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to find sum of frequencies
// of characters of S1 present in S2
void countTotalFrequencies(string S1, string S2)
{
 
  // Insert all characters of
  // string S1 in the set
  set<char> bset;
  for(auto x:S1)
    bset.insert(x);
  int count = 0;
 
  // Traverse the string S2
  for (auto x: S2)
  {
 
    // Check if X is present
    // in bset or not
    if (bset.find(x) != bset.end())
 
      // Increment count by 1
      count += 1;
  }
 
  // Finally, print the count
  cout << count << endl;
 
}
 
// Driver Code
int main()
{
   
  // Given strings
  string S1 = "geEksFOR";
  string S2 = "GeEksforgeEKS";
 
  countTotalFrequencies(S1, S2);
 
}
 
// This code is contributed by ipg2016107.

// Java program for the above approach
import java.util.HashSet;
 
class GFG{
 
// Function to find sum of frequencies
// of characters of S1 present in S2
static void countTotalFrequencies(String S1, String S2)
{
     
    // Insert all characters of
    // string S1 in the set
    HashSet<Character> bset = new HashSet<Character>();
    char[] S1arr = S1.toCharArray();
    char[] S2arr = S2.toCharArray();
     
    for(char x : S1arr)
        bset.add(x);
         
    int count = 0;
 
    // Traverse the string S2
    for(char x : S2arr)
    {
         
        // Check if X is present
        // in bset or not
        if (bset.contains(x))
 
            // Increment count by 1
            count += 1;
    }
 
    // Finally, print the count
    System.out.print(count);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given strings
    String S1 = "geEksFOR";
    String S2 = "GeEksforgeEKS";
 
    countTotalFrequencies(S1, S2);
}
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to find sum of frequencies
# of characters of S1 present in S2
def countTotalFrequencies(S1, S2):
 
    # Insert all characters of
    # string S1 in the set
    bset = set(S1)
    count = 0
 
    # Traverse the string S2
    for x in S2:
 
        # Check if X is present
        # in bset or not
        if x in bset:
 
            # Increment count by 1
            count += 1
 
    # Finally, print the count
    print(count)
 
# Driver Code
 
# Given strings
S1 = "geEksFOR"
S2 = "GeEksforgeEKS"
 
countTotalFrequencies(S1, S2)

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG {
     
// Function to find sum of frequencies
// of characters of S1 present in S2
static void countTotalFrequencies(string S1,
                                  string S2)
{
 
    // Insert all characters of
    // string S1 in the set
    HashSet<char> bset = new HashSet<char>();
 
    foreach(char x in S1)
        bset.Add(x);
         
    int count = 0;
 
    // Traverse the string S2
    foreach(char x in S2)
    {
 
        // Check if X is present
        // in bset or not
        if (bset.Contains(x))
 
            // Increment count by 1
            count += 1;
    }
     
    // Finally, print the count
    Console.Write(count);
}
 
// Driver code
static void Main()
{
     
    // Given strings
    string S1 = "geEksFOR";
    string S2 = "GeEksforgeEKS";
 
    countTotalFrequencies(S1, S2);
}
}
 
// This code is contributed by abhinavjain194

<script>
 
// Javascript program for the above approach
 
// Function to find sum of frequencies
// of characters of S1 present in S2
function countTotalFrequencies(S1, S2)
{
     
    // Insert all characters of
    // string S1 in the set
    var bset = new Set();
    for(var i = 0; i < S1.length; i++)
    {
        bset.add(S1[i]);
    }
     
    var count = 0;
     
    // Traverse the string S2
    for(var i = 0; i < S2.length; i++)
    {
     
        // Check if X is present
        // in bset or not
        if (bset.has(S2[i]))
         
            // Increment count by 1
            count += 1;
    }
     
    // Finally, print the count
    document.write(count);
}
 
// Driver Code
 
// Given strings
var S1 = "geEksFOR";
var S2 = "GeEksforgeEKS";
 
countTotalFrequencies(S1, S2);
 
// This code is contributed by rutvik_56
 
</script>

7

Complejidad temporal: O(N)
Espacio auxiliar: O(N)