Dadas dos strings s1 y s2 que consisten en alfabetos ingleses en minúsculas, la tarea es contar todos los pares de índices (i, j) de las strings dadas tal que s1[i] = s2[j] y todos los índices son distintos, es decir, si s1[i] se empareja con algún s2[j] , entonces estos dos caracteres no se emparejarán con ningún otro carácter.
Ejemplo
Entrada: s1 = “abcd”, s2 = “aad”
Salida: 2
(s1[0], s2[0]) y (s1[3], s2[2]) son los únicos pares válidos.
(s1[0], s2[1]) no se incluye porque s1[0] ya se emparejó con s2[0]
Entrada: s1 = “geeksforgeeks”, s2 = “platformforgeeks”
Salida: 8
Enfoque: Cuente las frecuencias de todos los caracteres de ambas strings. Ahora, para cada carácter, si la frecuencia de este carácter en la string s1 es freq1 y en la string s2 es freq2 , el total de pares válidos con este carácter será min(freq1, freq2) . La suma de este valor para todos los caracteres es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of
// valid indices pairs
int countPairs(string s1, int n1, string s2, int n2)
{
// To store the frequencies of characters
// of string s1 and s2
int freq1[26] = { 0 };
int freq2[26] = { 0 };
// To store the count of valid pairs
int i, count = 0;
// Update the frequencies of
// the characters of string s1
for (i = 0; i < n1; i++)
freq1[s1[i] - 'a']++;
// Update the frequencies of
// the characters of string s2
for (i = 0; i < n2; i++)
freq2[s2[i] - 'a']++;
// Find the count of valid pairs
for (i = 0; i < 26; i++)
count += (min(freq1[i], freq2[i]));
return count;
}
// Driver code
int main()
{
string s1 = "geeksforgeeks", s2 = "platformforgeeks";
int n1 = s1.length(), n2 = s2.length();
cout << countPairs(s1, n1, s2, n2);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the count of
// valid indices pairs
static int countPairs(String s1, int n1,
String s2, int n2)
{
// To store the frequencies of characters
// of string s1 and s2
int []freq1 = new int[26];
int []freq2 = new int[26];
Arrays.fill(freq1, 0);
Arrays.fill(freq2, 0);
// To store the count of valid pairs
int i, count = 0;
// Update the frequencies of
// the characters of string s1
for (i = 0; i < n1; i++)
freq1[s1.charAt(i) - 'a']++;
// Update the frequencies of
// the characters of string s2
for (i = 0; i < n2; i++)
freq2[s2.charAt(i) - 'a']++;
// Find the count of valid pairs
for (i = 0; i < 26; i++)
count += (Math.min(freq1[i], freq2[i]));
return count;
}
// Driver code
public static void main(String args[])
{
String s1 = "geeksforgeeks", s2 = "platformforgeeks";
int n1 = s1.length(), n2 = s2.length();
System.out.println(countPairs(s1, n1, s2, n2));
}
}
// This code is contributed by
// Surendra_Gangwar
Python3
# Python3 implementation of the approach
# Function to return the count of
# valid indices pairs
def countPairs(s1, n1, s2, n2) :
# To store the frequencies of characters
# of string s1 and s2
freq1 = [0] * 26;
freq2 = [0] * 26;
# To store the count of valid pairs
count = 0;
# Update the frequencies of
# the characters of string s1
for i in range(n1) :
freq1[ord(s1[i]) - ord('a')] += 1;
# Update the frequencies of
# the characters of string s2
for i in range(n2) :
freq2[ord(s2[i]) - ord('a')] += 1;
# Find the count of valid pairs
for i in range(26) :
count += min(freq1[i], freq2[i]);
return count;
# Driver code
if __name__ == "__main__" :
s1 = "geeksforgeeks";
s2 = "platformforgeeks";
n1 = len(s1) ;
n2 = len(s2);
print(countPairs(s1, n1, s2, n2));
# This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of
// valid indices pairs
static int countPairs(string s1, int n1,
string s2, int n2)
{
// To store the frequencies of
// characters of string s1 and s2
int []freq1 = new int[26];
int []freq2 = new int[26];
Array.Fill(freq1, 0);
Array.Fill(freq2, 0);
// To store the count of valid pairs
int i, count = 0;
// Update the frequencies of
// the characters of string s1
for (i = 0; i < n1; i++)
freq1[s1[i] - 'a']++;
// Update the frequencies of
// the characters of string s2
for (i = 0; i < n2; i++)
freq2[s2[i] - 'a']++;
// Find the count of valid pairs
for (i = 0; i < 26; i++)
count += (Math.Min(freq1[i],
freq2[i]));
return count;
}
// Driver code
public static void Main()
{
string s1 = "geeksforgeeks",
s2 = "platformforgeeks";
int n1 = s1.Length, n2 = s2.Length;
Console.WriteLine(countPairs(s1, n1, s2, n2));
}
}
// This code is contributed by
// Akanksha Rai
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the count of
// valid indices pairs
function countPairs(s1, n1, s2, n2)
{
// To store the frequencies of
// characters of string s1 and s2
let freq1 = new Array(26);
let freq2 = new Array(26);
freq1.fill(0);
freq2.fill(0);
// To store the count of valid pairs
let i, count = 0;
// Update the frequencies of
// the characters of string s1
for (i = 0; i < n1; i++)
freq1[s1[i].charCodeAt() - 'a'.charCodeAt()]++;
// Update the frequencies of
// the characters of string s2
for (i = 0; i < n2; i++)
freq2[s2[i].charCodeAt() - 'a'.charCodeAt()]++;
// Find the count of valid pairs
for (i = 0; i < 26; i++)
count += (Math.min(freq1[i], freq2[i]));
return count;
}
let s1 = "geeksforgeeks", s2 = "platformforgeeks";
let n1 = s1.length, n2 = s2.length;
document.write(countPairs(s1, n1, s2, n2));
</script>
8
Complejidad de tiempo: O(max(n1, n2))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ShivamChauhan5 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA