Recuento de distintos grupos de strings formadas después de realizar una operación equivalente

Dada una array arr[] de N strings que consisten en letras minúsculas, la tarea es encontrar el número de distintos grupos de strings formados después de realizar la operación equivalente.

Se dice que dos strings son equivalentes si existe el mismo carácter en ambas strings y si existe otra string que es equivalente a una de las strings en el grupo de strings equivalentes, entonces esa string también es equivalente a ese grupo.

Ejemplos:

Entrada: arr[] = {“a”, “b”, “ab”, “d”}
Salida: 2
Explicación:
Como las strings “b” y “ab” tienen ‘b’ como el mismo carácter, también son equivalentes “ab” y la string “a” tienen ‘a’ como el mismo carácter, por lo que las strings “a”, “b”, “ab” son equivalentes y “d” es otra string.

Por lo tanto, el conteo de distintos grupos de strings formadas es 2.

Entrada: arr[] = {“ab”, “bc”, “abc”}
Salida: 1

Enfoque: El problema dado se puede resolver usando Disjoint Set Union , la idea es atravesar la string y marcar todos los caracteres de la string actual como verdaderos y realizar la operación de unión en el primer carácter de la string actual con el carácter ‘a ‘ , y cuente el número diferente de padres en el vector padre y guárdelo. Siga los pasos a continuación para resolver el problema:

• Inicializa los vectores parent(27), rank(27, 0), total(26, false) y current(26, false) .
• Inicialice una variable, digamos distCount como 0 que almacena el recuento de strings distintas.
• Iterar sobre el rango [0, 27) usando la variable i y establecer el valor de parent[i] como i .
• Iterar sobre el rango [0, N) usando la variable i y realizar los siguientes pasos:
  • Itere sobre el rango [0, 26) usando la variable j y establezca current[j] en false .
  • Itere sobre los caracteres de la string arr[i] usando la variable ch y establezca current[ch – ‘a’] en true .
  • Itere sobre el rango [0, 26) usando la variable j y si actual[j] es verdadero, entonces establezca total[j] en verdadero y llame a la función Union(parent, rank, arr[i][0] – ‘a ‘, j) .
• Itere sobre el rango [0, 26) usando la variable i y verifique si total[i] es verdadero y Find(parent, i) es I si es verdadero, luego incremente el valor de distCount en 1 .
• Finalmente, imprime el valor de distCount .

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 perform the find operation
// to find the parent of a disjoint set
int Find(vector<int>& parent, int a)
{
    return parent[a]
           = (parent[a] == a ? a : Find(parent, parent[a]));
}
 
// Function to perform union operation
// of disjoint set union
void Union(vector<int>& parent,
           vector<int>& rank, int a,
           int b)
{
 
    // Find the parent of node a and b
    a = Find(parent, a);
    b = Find(parent, b);
 
    // Update the rank
    if (rank[a] == rank[b])
        rank[a]++;
    if (rank[a] > rank[b])
        parent[b] = a;
    else
        parent[a] = b;
}
 
// Function to find the number of distinct
// strings after performing the
// given operations
void numOfDistinctStrings(string arr[],
                          int N)
{
    // Stores the parent elements
    // of the sets
    vector<int> parent(27);
 
    // Stores the rank of the sets
    vector<int> rank(27, 0);
 
    for (int j = 0; j < 27; j++) {
        // Update parent[i] to i
        parent[j] = j;
    }
 
    // Stores the total characters
    // traversed through the strings
    vector<bool> total(26, false);
 
    // Stores the current characters
    // traversed through a string
    vector<bool> current(26, false);
 
    for (int i = 0; i < N; i++) {
 
        for (int j = 0; j < 26; j++) {
 
            // Update current[i] to false
            current[j] = false;
        }
 
        for (char ch : arr[i]) {
 
            // Update current[ch - 'a'] to true
            current[ch - 'a'] = true;
        }
 
        for (int j = 0; j < 26; j++) {
 
            // Check if current[j] is true
            if (current[j]) {
 
                // Update total[j] to true
                total[j] = true;
 
                // Add arr[i][0] - 'a' and
                // j elements to same set
                Union(parent, rank,
                      arr[i][0] - 'a', j);
            }
        }
    }
 
    // Stores the count of distinct strings
    int distCount = 0;
    for (int i = 0; i < 26; i++) {
 
        // Check total[i] is true and
        // parent of i is i only
        if (total[i] && Find(parent, i) == i) {
 
            // Increment the value of
            // distCount by 1
            distCount++;
        }
    }
 
    // Print the value of distCount
    cout << distCount << endl;
}
 
// Driver Code
int main()
{
    string arr[] = { "a", "ab", "b", "d" };
    int N = sizeof(arr) / sizeof(arr[0]);
    numOfDistinctStrings(arr, N);
 
    return 0;
}

# python program for the above approach
 
# Function to perform the find operation
# to find the parent of a disjoint set
def Find(parent, a):
    if parent[a] == a:
        parent[a] = a
        return parent[a]
    else:
        parent[a] = Find(parent, parent[a])
        return parent[a]
 
# Function to perform union operation
# of disjoint set union
def Union(parent, rank, a, b):
 
        # Find the parent of node a and b
    a = Find(parent, a)
    b = Find(parent, b)
 
    # Update the rank
    if (rank[a] == rank[b]):
        rank[a] += 1
    if (rank[a] > rank[b]):
        parent[b] = a
    else:
        parent[a] = b
 
# Function to find the number of distinct
# strings after performing the
# given operations
def numOfDistinctStrings(arr, N):
 
    # Stores the parent elements
    # of the sets
    parent = [0 for _ in range(27)]
 
    # Stores the rank of the sets
    rank = [0 for _ in range(27)]
 
    for j in range(0, 27):
        # Update parent[i] to i
        parent[j] = j
 
    # Stores the total characters
    # traversed through the strings
    total = [False for _ in range(26)]
 
    # Stores the current characters
    # traversed through a string
    current = [False for _ in range(26)]
 
    for i in range(0, N):
 
        for j in range(0, 26):
 
            # Update current[i] to false
            current[j] = False
 
        for ch in arr[i]:
 
            # Update current[ch - 'a'] to true
            current[ord(ch) - ord('a')] = True
 
        for j in range(0, 26):
 
            # Check if current[j] is true
            if (current[j]):
 
                # Update total[j] to true
                total[j] = True
 
                # Add arr[i][0] - 'a' and
                # j elements to same set
                Union(parent, rank, ord(arr[i][0]) - ord('a'), j)
 
    # Stores the count of distinct strings
    distCount = 0
    for i in range(0, 26):
 
        # Check total[i] is true and
        # parent of i is i only
        if (total[i] and Find(parent, i) == i):
 
            # Increment the value of
            # distCount by 1
            distCount += 1
 
    # Print the value of distCount
    print(distCount)
 
# Driver Code
if __name__ == "__main__":
 
    arr = ["a", "ab", "b", "d"]
    N = len(arr)
    numOfDistinctStrings(arr, N)
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG {
 
    // Function to perform the find operation
    // to find the parent of a disjoint set
    static int Find(int[] parent, int a)
    {
        return parent[a]
            = (parent[a] == a ? a
                              : Find(parent, parent[a]));
    }
 
    // Function to perform union operation
    // of disjoint set union
    static void Union(int[] parent, int[] rank, int a,
                      int b)
    {
 
        // Find the parent of node a and b
        a = Find(parent, a);
        b = Find(parent, b);
 
        // Update the rank
        if (rank[a] == rank[b])
            rank[a]++;
        if (rank[a] > rank[b])
            parent[b] = a;
        else
            parent[a] = b;
    }
 
    // Function to find the number of distinct
    // strings after performing the
    // given operations
    static void numOfDistinctStrings(string[] arr, int N)
    {
        // Stores the parent elements
        // of the sets
        int[] parent = new int[(27)];
 
        // Stores the rank of the sets
        int[] rank = new int[(27)];
 
        for (int j = 0; j < 27; j++) {
            // Update parent[i] to i
            parent[j] = j;
        }
 
        // Stores the total characters
        // traversed through the strings
        bool[] total = new bool[26];
 
        // Stores the current characters
        // traversed through a string
        bool[] current = new bool[26];
 
        for (int i = 0; i < N; i++) {
 
            for (int j = 0; j < 26; j++) {
 
                // Update current[i] to false
                current[j] = false;
            }
 
            foreach(char ch in arr[i])
            {
 
                // Update current[ch - 'a'] to true
                current[ch - 'a'] = true;
            }
 
            for (int j = 0; j < 26; j++) {
 
                // Check if current[j] is true
                if (current[j]) {
 
                    // Update total[j] to true
                    total[j] = true;
 
                    // Add arr[i][0] - 'a' and
                    // j elements to same set
                    Union(parent, rank, arr[i][0] - 'a', j);
                }
            }
        }
 
        // Stores the count of distinct strings
        int distCount = 0;
        for (int i = 0; i < 26; i++) {
 
            // Check total[i] is true and
            // parent of i is i only
            if (total[i] && Find(parent, i) == i) {
 
                // Increment the value of
                // distCount by 1
                distCount++;
            }
        }
 
        // Print the value of distCount
        Console.WriteLine(distCount);
    }
 
    // Driver Code
    public static void Main()
    {
        string[] arr = { "a", "ab", "b", "d" };
        int N = arr.Length;
        numOfDistinctStrings(arr, N);
    }
}
 
// This code is contributed by ukasp.

2

Complejidad de tiempo: O (N * log N), ya que estamos usando un bucle para atravesar N veces y la función de unión nos costará logN tiempo.
Espacio Auxiliar: O(1), ya que estamos usando un espacio constante de tamaño 27.