Se dice que dos strings están completas si al concatenarlas contienen los 26 alfabetos ingleses. Por ejemplo, “abcdefghi” y “jklmnopqrstuvwxyz” están completos ya que juntos tienen todos los caracteres de la ‘a’ a la ‘z’.
Nos dan dos conjuntos de tamaños n y m respectivamente y necesitamos encontrar el número de pares que están completos al concatenar cada string del conjunto 1 con cada string del conjunto 2.
Input : set1[] = {"abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc"}
set2[] = {"ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz"}
Output : 7
The total complete pairs that are forming are:
"abcdefghijklmnopqrstuvwxyz"
"abcdefghabcdefghijklmnopqrstuvwxyz"
"abcdefghdefghijklmnopqrstuvwxyz"
"geeksforgeeksabcdefghijklmnopqrstuvwxyz"
"lmnopqrstabcdefghijklmnopqrstuvwxyz"
"abcabcdefghijklmnopqrstuvwxyz"
"abcdefghijklmnopqrstuvwxyz"
Método 1 (método ingenuo): una solución simple es considerar todos los pares de strings, concatenarlas y luego verificar si la string concatenada tiene todos los caracteres de ‘a’ a ‘z’ usando una array de frecuencia.
Implementación:
C++
// C++ implementation for find pairs of complete
// strings.
#include <iostream>
using namespace std;
// Returns count of complete pairs from set[0..n-1]
// and set2[0..m-1]
int countCompletePairs(string set1[], string set2[],
int n, int m)
{
int result = 0;
// Consider all pairs of both strings
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Create a concatenation of current pair
string concat = set1[i] + set2[j];
// Compute frequencies of all characters
// in the concatenated string.
int frequency[26] = { 0 };
for (int k = 0; k < concat.length(); k++)
frequency[concat[k] - 'a']++;
// If frequency of any character is not
// greater than 0, then this pair is not
// complete.
int i;
for (i = 0; i < 26; i++)
if (frequency[i] < 1)
break;
if (i == 26)
result++;
}
}
return result;
}
// Driver code
int main()
{
string set1[] = { "abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc" };
string set2[] = { "ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz" };
int n = sizeof(set1) / sizeof(set1[0]);
int m = sizeof(set2) / sizeof(set2[0]);
cout << countCompletePairs(set1, set2, n, m);
return 0;
}
Java
// Java implementation for find pairs of complete
// strings.
class GFG {
// Returns count of complete pairs from set[0..n-1]
// and set2[0..m-1]
static int countCompletePairs(String set1[], String set2[],
int n, int m)
{
int result = 0;
// Consider all pairs of both strings
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Create a concatenation of current pair
String concat = set1[i] + set2[j];
// Compute frequencies of all characters
// in the concatenated String.
int frequency[] = new int[26];
for (int k = 0; k < concat.length(); k++) {
frequency[concat.charAt(k) - 'a']++;
}
// If frequency of any character is not
// greater than 0, then this pair is not
// complete.
int k;
for (k = 0; k < 26; k++) {
if (frequency[k] < 1) {
break;
}
}
if (k == 26) {
result++;
}
}
}
return result;
}
// Driver code
static public void main(String[] args)
{
String set1[] = { "abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc" };
String set2[] = { "ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz" };
int n = set1.length;
int m = set2.length;
System.out.println(countCompletePairs(set1, set2, n, m));
}
}
// This code is contributed by PrinciRaj19992
Python3
# Python3 implementation for find pairs of complete
# strings.
# Returns count of complete pairs from set[0..n-1]
# and set2[0..m-1]
def countCompletePairs(set1,set2,n,m):
result = 0
# Consider all pairs of both strings
for i in range(n):
for j in range(m):
# Create a concatenation of current pair
concat = set1[i] + set2[j]
# Compute frequencies of all characters
# in the concatenated String.
frequency = [0 for i in range(26)]
for k in range(len(concat)):
frequency[ord(concat[k]) - ord('a')] += 1
# If frequency of any character is not
# greater than 0, then this pair is not
# complete.
k = 0
while(k<26):
if (frequency[k] < 1):
break
k += 1
if (k == 26):
result += 1
return result
# Driver code
set1=["abcdefgh", "geeksforgeeks", "lmnopqrst", "abc"]
set2=["ijklmnopqrstuvwxyz", "abcdefghijklmnopqrstuvwxyz", "defghijklmnopqrstuvwxyz"]
n = len(set1)
m = len(set2)
print(countCompletePairs(set1, set2, n, m))
# This code is contributed by shinjanpatra
C#
// C# implementation for find pairs of complete
// strings.
using System;
class GFG {
// Returns count of complete pairs from set[0..n-1]
// and set2[0..m-1]
static int countCompletePairs(string[] set1, string[] set2,
int n, int m)
{
int result = 0;
// Consider all pairs of both strings
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Create a concatenation of current pair
string concat = set1[i] + set2[j];
// Compute frequencies of all characters
// in the concatenated String.
int[] frequency = new int[26];
for (int k = 0; k < concat.Length; k++) {
frequency[concat[k] - 'a']++;
}
// If frequency of any character is not
// greater than 0, then this pair is not
// complete.
int l;
for (l = 0; l < 26; l++) {
if (frequency[l] < 1) {
break;
}
}
if (l == 26) {
result++;
}
}
}
return result;
}
// Driver code
static public void Main()
{
string[] set1 = { "abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc" };
string[] set2 = { "ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz" };
int n = set1.Length;
int m = set2.Length;
Console.Write(countCompletePairs(set1, set2, n, m));
}
}
// This article is contributed by Ita_c.
Javascript
<script>
// Javascript implementation for find pairs of complete
// strings.
// Returns count of complete pairs from set[0..n-1]
// and set2[0..m-1]
function countCompletePairs(set1,set2,n,m)
{
let result = 0;
// Consider all pairs of both strings
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
// Create a concatenation of current pair
let concat = set1[i] + set2[j];
// Compute frequencies of all characters
// in the concatenated String.
let frequency = new Array(26);
for(let i= 0;i<26;i++)
{
frequency[i]=0;
}
for (let k = 0; k < concat.length; k++) {
frequency[concat[k].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
// If frequency of any character is not
// greater than 0, then this pair is not
// complete.
let k;
for (k = 0; k < 26; k++) {
if (frequency[k] < 1) {
break;
}
}
if (k == 26) {
result++;
}
}
}
return result;
}
// Driver code
let set1=["abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc"];
let set2=["ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz"]
let n = set1.length;
let m=set2.length;
document.write(countCompletePairs(set1, set2, n, m));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
7
Complejidad Temporal: O(n * m * k)
Espacio Auxiliar: O(1)
Método 2 (Método optimizado con manipulación de bits): en este método, comprimimos la array de frecuencias en un número entero. Asignamos a cada bit de ese entero un carácter y lo establecemos en 1 cuando se encuentra el carácter. Realizamos esto para todas las strings en ambos conjuntos. Finalmente, solo comparamos los dos enteros en los conjuntos y si al combinarlos todos los bits están configurados, forman un par de strings completo.
Implementación:
C++14
// C++ program to find count of complete pairs
#include <iostream>
using namespace std;
// Returns count of complete pairs from set[0..n-1]
// and set2[0..m-1]
int countCompletePairs(string set1[], string set2[],
int n, int m)
{
int result = 0;
// con_s1[i] is going to store an integer whose
// set bits represent presence/absence of characters
// in string set1[i].
// Similarly con_s2[i] is going to store an integer
// whose set bits represent presence/absence of
// characters in string set2[i]
int con_s1[n], con_s2[m];
// Process all strings in set1[]
for (int i = 0; i < n; i++) {
// initializing all bits to 0
con_s1[i] = 0;
for (int j = 0; j < set1[i].length(); j++) {
// Setting the ascii code of char s[i][j]
// to 1 in the compressed integer.
con_s1[i] = con_s1[i] | (1 << (set1[i][j] - 'a'));
}
}
// Process all strings in set2[]
for (int i = 0; i < m; i++) {
// initializing all bits to 0
con_s2[i] = 0;
for (int j = 0; j < set2[i].length(); j++) {
// setting the ascii code of char s[i][j]
// to 1 in the compressed integer.
con_s2[i] = con_s2[i] | (1 << (set2[i][j] - 'a'));
}
}
// assigning a variable whose all 26 (0..25)
// bits are set to 1
long long complete = (1 << 26) - 1;
// Now consider every pair of integer in con_s1[]
// and con_s2[] and check if the pair is complete.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// if all bits are set, the strings are
// complete!
if ((con_s1[i] | con_s2[j]) == complete)
result++;
}
}
return result;
}
// Driver code
int main()
{
string set1[] = { "abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc" };
string set2[] = { "ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz" };
int n = sizeof(set1) / sizeof(set1[0]);
int m = sizeof(set2) / sizeof(set2[0]);
cout << countCompletePairs(set1, set2, n, m);
return 0;
}
Java
// Java program to find count of complete pairs
class GFG {
// Returns count of complete pairs from set[0..n-1]
// and set2[0..m-1]
static int countCompletePairs(String set1[], String set2[],
int n, int m)
{
int result = 0;
// con_s1[i] is going to store an integer whose
// set bits represent presence/absence of characters
// in string set1[i].
// Similarly con_s2[i] is going to store an integer
// whose set bits represent presence/absence of
// characters in string set2[i]
int[] con_s1 = new int[n];
int[] con_s2 = new int[m];
// Process all strings in set1[]
for (int i = 0; i < n; i++) {
// initializing all bits to 0
con_s1[i] = 0;
for (int j = 0; j < set1[i].length(); j++) {
// Setting the ascii code of char s[i][j]
// to 1 in the compressed integer.
con_s1[i] = con_s1[i] | (1 << (set1[i].charAt(j) - 'a'));
}
}
// Process all strings in set2[]
for (int i = 0; i < m; i++) {
// initializing all bits to 0
con_s2[i] = 0;
for (int j = 0; j < set2[i].length(); j++) {
// setting the ascii code of char s[i][j]
// to 1 in the compressed integer.
con_s2[i] = con_s2[i] | (1 << (set2[i].charAt(j) - 'a'));
}
}
// assigning a variable whose all 26 (0..25)
// bits are set to 1
long complete = (1 << 26) - 1;
// Now consider every pair of integer in con_s1[]
// and con_s2[] and check if the pair is complete.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// if all bits are set, the strings are
// complete!
if ((con_s1[i] | con_s2[j]) == complete) {
result++;
}
}
}
return result;
}
// Driver code
public static void main(String args[])
{
String set1[] = { "abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc" };
String set2[] = { "ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz" };
int n = set1.length;
int m = set2.length;
System.out.println(countCompletePairs(set1, set2, n, m));
}
}
// This code contributed by Rajput-Ji
C#
// C# program to find count of complete pairs
using System;
class GFG {
// Returns count of complete pairs from set[0..n-1]
// and set2[0..m-1]
static int countCompletePairs(String[] set1, String[] set2,
int n, int m)
{
int result = 0;
// con_s1[i] is going to store an integer whose
// set bits represent presence/absence of characters
// in string set1[i].
// Similarly con_s2[i] is going to store an integer
// whose set bits represent presence/absence of
// characters in string set2[i]
int[] con_s1 = new int[n];
int[] con_s2 = new int[m];
// Process all strings in set1[]
for (int i = 0; i < n; i++) {
// initializing all bits to 0
con_s1[i] = 0;
for (int j = 0; j < set1[i].Length; j++) {
// Setting the ascii code of char s[i][j]
// to 1 in the compressed integer.
con_s1[i] = con_s1[i] | (1 << (set1[i][j] - 'a'));
}
}
// Process all strings in set2[]
for (int i = 0; i < m; i++) {
// initializing all bits to 0
con_s2[i] = 0;
for (int j = 0; j < set2[i].Length; j++) {
// setting the ascii code of char s[i][j]
// to 1 in the compressed integer.
con_s2[i] = con_s2[i] | (1 << (set2[i][j] - 'a'));
}
}
// assigning a variable whose all 26 (0..25)
// bits are set to 1
long complete = (1 << 26) - 1;
// Now consider every pair of integer in con_s1[]
// and con_s2[] and check if the pair is complete.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// if all bits are set, the strings are
// complete!
if ((con_s1[i] | con_s2[j]) == complete) {
result++;
}
}
}
return result;
}
// Driver code
public static void Main(String[] args)
{
String[] set1 = { "abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc" };
String[] set2 = { "ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz" };
int n = set1.Length;
int m = set2.Length;
Console.WriteLine(countCompletePairs(set1, set2, n, m));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to find count of complete pairs
# Returns count of complete pairs from set[0..n-1]
# and set2[0..m-1]
def countCompletePairs(set1, set2, n, m):
result = 0
# con_s1[i] is going to store an integer whose
# set bits represent presence/absence of characters
# in set1[i].
# Similarly con_s2[i] is going to store an integer
# whose set bits represent presence/absence of
# characters in set2[i]
con_s1, con_s2 = [0] * n, [0] * m
# Process all strings in set1[]
for i in range(n):
# initializing all bits to 0
con_s1[i] = 0
for j in range(len(set1[i])):
# Setting the ascii code of char s[i][j]
# to 1 in the compressed integer.
con_s1[i] = con_s1[i] | (1 << (ord(set1[i][j]) - ord('a')))
# Process all strings in set2[]
for i in range(m):
# initializing all bits to 0
con_s2[i] = 0
for j in range(len(set2[i])):
# setting the ascii code of char s[i][j]
# to 1 in the compressed integer.
con_s2[i] = con_s2[i] | (1 << (ord(set2[i][j]) - ord('a')))
# assigning a variable whose all 26 (0..25)
# bits are set to 1
complete = (1 << 26) - 1
# Now consider every pair of integer in con_s1[]
# and con_s2[] and check if the pair is complete.
for i in range(n):
for j in range(m):
# if all bits are set, the strings are
# complete!
if ((con_s1[i] | con_s2[j]) == complete):
result += 1
return result
# Driver code
if __name__ == '__main__':
set1 = ["abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc"]
set2 = ["ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz"]
n = len(set1)
m = len(set2)
print(countCompletePairs(set1, set2, n, m))
# This code is contributed by mohit kumar 29
Javascript
<script>
// Javascript program to find count of complete pairs
// Returns count of complete pairs from set[0..n-1]
// and set2[0..m-1]
function countCompletePairs(set1,set2,n,m)
{
let result = 0;
// con_s1[i] is going to store an integer whose
// set bits represent presence/absence of characters
// in string set1[i].
// Similarly con_s2[i] is going to store an integer
// whose set bits represent presence/absence of
// characters in string set2[i]
let con_s1 = new Array(n);
let con_s2 = new Array(m);
// Process all strings in set1[]
for (let i = 0; i < n; i++) {
// initializing all bits to 0
con_s1[i] = 0;
for (let j = 0; j < set1[i].length; j++) {
// Setting the ascii code of char s[i][j]
// to 1 in the compressed integer.
con_s1[i] = con_s1[i] |
(1 << (set1[i][j].charCodeAt(0) - 'a'.charCodeAt(0)));
}
}
// Process all strings in set2[]
for (let i = 0; i < m; i++) {
// initializing all bits to 0
con_s2[i] = 0;
for (let j = 0; j < set2[i].length; j++) {
// setting the ascii code of char s[i][j]
// to 1 in the compressed integer.
con_s2[i] = con_s2[i] |
(1 << (set2[i][j].charCodeAt(0) - 'a'.charCodeAt(0)));
}
}
// assigning a variable whose all 26 (0..25)
// bits are set to 1
let complete = (1 << 26) - 1;
// Now consider every pair of integer in con_s1[]
// and con_s2[] and check if the pair is complete.
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
// if all bits are set, the strings are
// complete!
if ((con_s1[i] | con_s2[j]) == complete) {
result++;
}
}
}
return result;
}
// Driver code
let set1=["abcdefgh", "geeksforgeeks",
"lmnopqrst", "abc"];
let set2=["ijklmnopqrstuvwxyz",
"abcdefghijklmnopqrstuvwxyz",
"defghijklmnopqrstuvwxyz" ]
let n = set1.length;
let m = set2.length;
document.write(countCompletePairs(set1, set2, n, m));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
7
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Rishabh Jain . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA