# Count of distinct groups of strings formed after performing equivalent operation

Given an array **arr[] **of** N **strings consisting of lowercase alphabets, the task is to find the number of distinct groups of strings formed after performing the equivalent operation.

Two strings are said to be

equivalentif there exists thesamecharacter in both the strings and if there exists another string that is equivalent to one of the strings in the group of equivalent string then that string is also equivalent to that group.Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

**Examples:**

Input:arr[] = {“a”, “b”, “ab”, “d”}Output:2Explanation:

As strings “b” and “ab” have ‘b’ as the same character, they are equivalent also “ab” and the string”a” have ‘a’ as the same character, so the strings “a”, “b”, “ab” are equivalent and “d” is another string.Therefore, the count of distinct group of strings formed is 2.

Input:arr[] = {“ab”, “bc”, “abc”}Output:1

**Approach:** The given problem can be solved using the Disjoint Set Union, the idea is to traverse the string and mark all the **characters** of the current string as **true** and perform the **union** operation on the first character of the current string with the character **‘a’**, and count the **different** number of parents in the **parent** vector and store it. Follow the below steps to solve the problem:

- Initialize the vectors
**parent(27), rank(27, 0), total(26, false)**, and**current(26, false)**. - Initialize a variable, say
**distCount**as**0**that stores the count of distinct strings. - Iterate over the range
**[0, 27)**using the variable**i**and set the value of**parent[i]**as**i**. - Iterate over the range
**[0, N)**using the variable**i**and perform the following steps:- Iterate over the range
**[0, 26)**using the variable**j**and set**current[j]**to**false**. - Iterate over the characters of the string
**arr[i]**using the variable**ch**and set**current[ch – ‘a’]**to**true**. - Iterate over the range
**[0, 26)**using the variable**j**and if**current[j]**is true then set**total[j]**to**true**and call for the function**Union(parent, rank, arr[i][0] – ‘a’, j)**.

- Iterate over the range
- Iterate over the range
**[0, 26)**using the variable**i**and check if**total[i]**is**true**and**Find(parent, i)**is**I**if it is true then increment the value of**distCount**by**1**. - Finally, print the value of
**distCount**.

Below is the implementation of the above approach:

## C++

`// 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;` `}` |

## Python3

`# 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#

`// 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.` |

**Output:**

2

**Time Complexity:** O(N*log N)**Auxiliary Space:** O(N)