Count of Distinct Groups of Strings Formed after Performing an Equivalent Operation

Soumya Agrawal
Last Updated: May 13, 2022

 

Introduction

As the title of this article suggests, we will be discussing the problem based on the famous data structure Strings. Strings are a sequence of characters like “abc” is a string containing ‘a’, ‘b,’ ‘c’ are the sequence of characters.

 

String offers various methods for simplicity in programming. In Java, a string is immutable, meaning it cannot be changed once created.

 

We will discuss a problem where we have to count the distinct group of strings formed after checking the equivalence between the two strings.

Without any delays, let’s move to our problem statement.

Problem Statement 

 

We are given an array of strings, and we aim to find the number of distinct groups formed after performing an equivalent operation.


Now, What do you mean by an equivalent operation?

If the same character is present in both strings, then the two strings are said to be equivalent, and if there is another string that matches one of the strings in a group of equivalent strings, then that string is also equivalent to that group.

 

Example:

 

Input: {“ab”, “bc”, “abc”}

 

Output: 2

 

Explanation:

 

The string “ab” and “bc” have a common character as ‘b,’ and strings “bc,” and “abc” also have a common character as ‘bc’ as well as strings “b” and “abc” also have a character in common, i.e., ‘ab’ so the strings “ab”, “bc”, “abc” are equivalent.

 

Therefore the distinct group of strings is ‘1’.

 

Approach

 

We can use the approach of Disjoint Set Union to solve this question. We will consider all the Strings to be nodes of a graph. We will connect two nodes if the Strings have a common character. After connecting all the nodes using DSU, we just need to find the number of Disconnected components. 

Refer to the below implementation of the above approach.

 

Implementation

 

import java.util.*;
import java.io.*; 
  
public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String a[] = new String[n];
		for(int i=0;i<n;i++) {
			a[i] = sc.next();
		}
		System.out.println(solve(a, n));
	}
	static int solve(String a[], int n) {
		DSU dsu = new DSU(26);
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<a[i].length();j++) {
				dsu.join(a[i].charAt(j)-'a', j);
			}
		}
		
		int cnt = 0;
		for(int i=0;i<n;i++) {
			if(dsu.findPar(i) == i) {
				cnt++;
			}
		}
		
		return cnt;
	}
}
class DSU {
	int par[];
	int size[];
	DSU(int n) {
		par = new int[n];
		size = new int[n];
		Arrays.fill(size, 1);
		for(int i=0;i<n;i++) par[i] = i;
	}
	int findPar(int x) {
		if(x == par[x]) return x;
		
		return par[x] = findPar(par[x]);
	}
	boolean join(int u,int v) {
		int fu = findPar(u);
		int fv = findPar(v);
		if(fu!=fv) {
			if(size[fu]>size[fv]) {
				par[fv] = fu;
				size[fu] += size[fv];
			}
			else {
				par[fu] = fv;
				size[fv] += size[fu];
			}
			return true;
		}
		else return false;
	}
}

 

3
ab
bc
abc

 

Output
 

1

FAQs

  1. What is the role of Disjoint Set in data structures?
    A disjoint set is used to find the number of disconnected components in a graph or join the node satisfying a particular condition.
     
  2. What is the time complexity to solve this problem?
    The time complexity to solve the problem in O(N * log(N))

 

Key Takeaways

This blog has covered the problem based on Strings in the Java language, where we have to count the group of distinct strings after checking the equivalence between them. 

 

You can give it a shot to this blog for guidance to master the Graph Algorithms.

 

You can use CodeStudio for various DSA questions typically asked in interviews for more practice. It will help you in mastering efficient coding techniques.

 

Was this article helpful ?
0 upvotes