Given an array S of strings of size N, the task is to check if it is possible to make all strings equal in any number of operations. In one operation, any character can be removed from the string and inserted at any arbitrary position in the same or different string. If the strings can be made equal, return the minimum number of operations required along with “Yes“, else return “No“.
Examples:
Input: N = 3, S = {aaa, bbb, ccc}
Output: Yes 6
Explanation: All three strings can be made equal to string abc, in minimum 6 operations
- {aaa, bbb, ccc} -> {aa, abbb, ccc}
- {aa, abbb, ccc} -> {a, abbb, accc}
- {a, abbb, accc} -> {ab, abb, accc}
- {ab, abb, accc} -> {ab, ab, abccc}
- {ab, ab, abccc} -> {abc, ab, abcc}
- {abc, ab, abccc} -> {abc, abc, abc}
Input: N = 3, S = {aba, bbb, cda}
Output: No
Approach: The idea to make all the strings equal, can be achieved if the letters should be distributed equally in all the strings. i.e. the frequency of every character should be divisible by N. Follow the steps below to solve the given problem:
- Initialize a vector, say freq[] to store the frequency of each character of the string.
- Traverse the array of strings.
- Store the frequency of each character in the vector hashmap.
- Finally, check if any character’s frequency is not a multiple of N then print No
- Else, Divide the frequency of each character with N for equal distribution among the N strings
- The resultant answer will be the count of extra characters in the original string with respect to the resultant equal string
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if strings// can be formed equal or notvoid solve(string S[], int N){ // Vector to store the frequency // of characters vector<int> freq(26, 0); // Traversing the array of strings for (int i = 0; i < N; i++) { // Traversing characters of the // string for (auto x : S[i]) { // Updating the frequency freq[x - 'a']++; } } // Checking for each character of // alphabet for (int i = 0; i < 26; i++) { // If frequency is not multiple // of N if (freq[i] % N != 0) { cout << "No\n"; return; } } // Divide frequency of each character // with N for (int i = 0; i < 26; i++) freq[i] /= N; // Store the count of minimum // operations int ans = 0; for (int i = 0; i < N; i++) { // Store frequencies of characters // in the original string vector<int> vis(26, 0); for (char c : S[i]) vis++; // Get the count of extra characters for (int i = 0; i < 26; i++) { if (freq[i] > 0 && vis[i] > 0) { ans += abs(freq[i] - vis[i]); } } } cout << "Yes " << ans << endl; return;}// Driver functionint main(){ int N = 3; string S[N] = { "aaa", "bbb", "ccc" }; solve(S, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check if Strings// can be formed equal or notstatic void solve(String S[], int N){ // Vector to store the frequency // of characters int []freq = new int[26]; // Traversing the array of Strings for (int i = 0; i < N; i++) { // Traversing characters of the // String for (int x : S[i].toCharArray()) { // Updating the frequency freq[x - 'a']++; } } // Checking for each character of // alphabet for (int i = 0; i < 26; i++) { // If frequency is not multiple // of N if (freq[i] % N != 0) { System.out.print("No\n"); return; } } // Divide frequency of each character // with N for (int i = 0; i < 26; i++) freq[i] /= N; // Store the count of minimum // operations int ans = 0; for (int s = 0; s < N; s++) { // Store frequencies of characters // in the original String int []vis = new int[26]; for (char c : S[s].toCharArray()) vis++; // Get the count of extra characters for (int i = 0; i < 26; i++) { if (freq[i] > 0 && vis[i] > 0) { ans += Math.abs(freq[i] - vis[i]); } } } System.out.print("Yes " + ans +"\n"); return;}// Driver functionpublic static void main(String[] args){ int N = 3; String S[] = { "aaa", "bbb", "ccc" }; solve(S, N);}}// This code is contributed by shikhasingrajput |
Python3
# python program for the above approach# Function to check if strings# can be formed equal or notdef solve(S, N): # Vector to store the frequency # of characters freq = [0 for _ in range(26)] # Traversing the array of strings for i in range(0, N): # Traversing characters of the # string for x in S[i]: # Updating the frequency freq[ord(x) - ord('a')] += 1 # Checking for each character of # alphabet for i in range(0, 26): # If frequency is not multiple # of N if (freq[i] % N != 0): print("No") return # Divide frequency of each character # with N for i in range(0, 26): freq[i] //= N # Store the count of minimum # operations ans = 0 for i in range(0, N): # Store frequencies of characters # in the original string vis = [0 for _ in range(26)] for c in S[i]: vis[ord(c) - ord('a')] += 1 # Get the count of extra characters for i in range(0, 26): if (freq[i] > 0 and vis[i] > 0): ans += abs(freq[i] - vis[i]) print(f"Yes {ans}") return# Driver functionif __name__ == "__main__": N = 3 S = ["aaa", "bbb", "ccc"] solve(S, N)# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;class GFG{// Function to check if Strings// can be formed equal or notstatic void solve(String []S, int N){ // List to store the frequency // of characters int []freq = new int[26]; // Traversing the array of Strings for(int i = 0; i < N; i++) { // Traversing characters of the // String foreach (int x in S[i].ToCharArray()) { // Updating the frequency freq[x - 'a']++; } } // Checking for each character of // alphabet for(int i = 0; i < 26; i++) { // If frequency is not multiple // of N if (freq[i] % N != 0) { Console.Write("No\n"); return; } } // Divide frequency of each character // with N for(int i = 0; i < 26; i++) freq[i] /= N; // Store the count of minimum // operations int ans = 0; for(int s = 0; s < N; s++) { // Store frequencies of characters // in the original String int []vis = new int[26]; foreach (char c in S[s].ToCharArray()) vis++; // Get the count of extra characters for(int i = 0; i < 26; i++) { if (freq[i] > 0 && vis[i] > 0) { ans += Math.Abs(freq[i] - vis[i]); } } } Console.Write("Yes " + ans + "\n"); return;}// Driver codepublic static void Main(String[] args){ int N = 3; String []S = { "aaa", "bbb", "ccc" }; solve(S, N);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Function to check if strings// can be formed equal or notfunction solve(S, N) { // Vector to store the frequency // of characters let freq = new Array(26).fill(0); // Traversing the array of strings for (let i = 0; i < N; i++) { // Traversing characters of the // string for (x of S[i]) { // Updating the frequency freq[x.charCodeAt(0) - 'a'.charCodeAt(0)]++; } } // Checking for each character of // alphabet for (let i = 0; i < 26; i++) { // If frequency is not multiple // of N if (freq[i] % N != 0) { document.write("No<br>"); return; } } // Divide frequency of each character // with N for (let i = 0; i < 26; i++) freq[i] = Math.floor(freq[i] / N); // Store the count of minimum // operations let ans = 0; for (let i = 0; i < N; i++) { // Store frequencies of characters // in the original string let vis = new Array(26).fill(0); for (c of S[i]) vis++; // Get the count of extra characters for (let i = 0; i < 26; i++) { if (freq[i] > 0 && vis[i] > 0) { ans += Math.abs(freq[i] - vis[i]); } } } document.write("Yes " + ans); return;}// Driver functionlet N = 3;let S = ["aaa", "bbb", "ccc"];solve(S, N);// This code is contributed by saurabh_jaiswal.</script> |
Output
Yes 6
Time Complexity: O(N*26)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
