Given an array, arr[] of N strings and a string T of size M, the task is to check if it is possible to make all the strings in the array arr[] same as the string T by removing any character from one string, say arr[i] and inserting it at any position to another string arr[j] any number of times.
Examples:
Input: arr[] = {“abc”, “abb”, “acc”}, T = “abc”
Output: Yes
Explanation:
Below is one of the possible way to make the all strings in the array to the string T is:
- Remove character at index 2 of the string arr[1](= “abb”) and then insert it at the index 1 of the string arr[2](= “acc”). After this the array modifies to {“abc”, “”ab”, “abcc”}.
- Remove character at index 3 of the string arr[2](= “abcc”) and then insert it at the index 2 of the string arr[1]( = “ab”). After this the array modifies to {“abc”, “”abc”, “abc”}.
After the above steps, all the strings of the array arr[] are equal to the string T(= abc). Therefore, print Yes.
Input: arr[] = {“abc”, “bbb”, “ccc”}, T = “abc”
Output: No
Approach: The given problem can be solved based on the following observation that the output will be “Yes” if and only if the following conditions are satisfied:
- None the string contains any character which is not present in T.
- All the characters of T must be present N times in all the given strings of S[] combined.
Follow the steps to solve the problem:
- Initialize two arrays, say freqS[256] and freqT[256] with value 0 to store the frequency of characters present in all strings of the array, arr[] and the string T respectively.
- Traverse the given array of strings arr[] and store the frequency of character for every string in the array freqS[].
- Iterate over the characters of the string T and store the frequency of character of the string T in the array freqT[].
- Iterate in the range [0, 255] using the variable i and perform the following steps:
- If the value of freqS[i] and freqT[i] are 0 or the value of freqS[i] is equal to N*freq[T], then continue the iteration.
- Otherwise, initialize a boolean variable, say A as true and break out of the loop.
- After completing the above steps, if the value of A is true, then print “No”. Otherwise, print “Yes“.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to check if it possible// to make all the strings equal to// the string Tstring checkIfPossible(int N, string arr[], string T){ // Stores the frequency of all // the strings in the array arr[] int freqS[256] = {0}; // Stores the frequency of the // string T int freqT[256] = {0}; // Iterate over the characters // of the string T for (char ch : T) { freqT[ch - 'a']++; } // Iterate in the range [0, N-1] for (int i = 0; i < N; i++) { // Iterate over the characters // of the string arr[i] for (char ch : arr[i]) { freqS[ch - 'a']++; } } for (int i = 0; i < 256; i++) { // If freqT[i] is 0 and // freqS[i] is not 0 if (freqT[i] == 0 && freqS[i] != 0) { return "No"; } // If freqS[i] is 0 and // freqT[i] is not 0 else if (freqS[i] == 0 && freqT[i] != 0) { return "No"; } // If freqS[i] is not freqT[i]*N else if (freqT[i] != 0 && freqS[i] != (freqT[i] * N)) { return "No"; } } // Otherwise, return "Yes" return "Yes";}// Driver Codeint main() { string arr[] = { "abc", "abb", "acc" }; string T = "abc"; int N = sizeof(arr) / sizeof(arr[0]); cout << checkIfPossible(N, arr, T); return 0;}// This code is contributed by Dharanendra L V. |
Java
// Java program for the above approachpublic class GFG { // Function to check if it possible // to make all the strings equal to // the string T static String checkIfPossible( int N, String[] arr, String T) { // Stores the frequency of all // the strings in the array arr[] int[] freqS = new int[256]; // Stores the frequency of the // string T int[] freqT = new int[256]; // Iterate over the characters // of the string T for (char ch : T.toCharArray()) { freqT[ch - 'a']++; } // Iterate in the range [0, N-1] for (int i = 0; i < N; i++) { // Iterate over the characters // of the string arr[i] for (char ch : arr[i].toCharArray()) { freqS[ch - 'a']++; } } for (int i = 0; i < 256; i++) { // If freqT[i] is 0 and // freqS[i] is not 0 if (freqT[i] == 0 && freqS[i] != 0) { return "No"; } // If freqS[i] is 0 and // freqT[i] is not 0 else if (freqS[i] == 0 && freqT[i] != 0) { return "No"; } // If freqS[i] is not freqT[i]*N else if (freqT[i] != 0 && freqS[i] != (freqT[i] * N)) { return "No"; } } // Otherwise, return "Yes" return "Yes"; } // Driver Code public static void main(String[] args) { String[] arr = { "abc", "abb", "acc" }; String T = "abc"; int N = arr.length; System.out.println( checkIfPossible(N, arr, T)); }} |
Python3
# Python3 program for the above approach# Function to check if it possible# to make all the strings equal to# the Tdef checkIfPossible(N, arr, T): # Stores the frequency of all # the strings in the array arr[] freqS = [0] * 256 # Stores the frequency of the # T freqT = [0] * 256 # Iterate over the characters # of the T for ch in T: freqT[ord(ch) - ord('a')] += 1 # Iterate in the range [0, N-1] for i in range(N): # Iterate over the characters # of the arr[i] for ch in arr[i]: freqS[ord(ch) - ord('a')] += 1 for i in range(256): # If freqT[i] is 0 and # freqS[i] is not 0 if (freqT[i] == 0 and freqS[i] != 0): return "No" # If freqS[i] is 0 and # freqT[i] is not 0 elif (freqS[i] == 0 and freqT[i] != 0): return "No" # If freqS[i] is not freqT[i]*N elif (freqT[i] != 0 and freqS[i]!= (freqT[i] * N)): return "No" # Otherwise, return "Yes" return "Yes"# Driver Codeif __name__ == '__main__': arr = [ "abc", "abb", "acc" ] T = "abc" N = len(arr) print(checkIfPossible(N, arr, T))# This code is contributed by mohit kumar 29 |
C#
// c# program for the above approachusing System;public class GFG { // Function to check if it possible // to make all the strings equal to // the string T static string checkIfPossible(int N, string[] arr, string T) { // Stores the frequency of all // the strings in the array arr[] int[] freqS = new int[256]; // Stores the frequency of the // string T int[] freqT = new int[256]; // Iterate over the characters // of the string T foreach(char ch in T.ToCharArray()) { freqT[ch - 'a']++; } // Iterate in the range [0, N-1] for (int i = 0; i < N; i++) { // Iterate over the characters // of the string arr[i] foreach(char ch in arr[i].ToCharArray()) { freqS[ch - 'a']++; } } for (int i = 0; i < 256; i++) { // If freqT[i] is 0 and // freqS[i] is not 0 if (freqT[i] == 0 && freqS[i] != 0) { return "No"; } // If freqS[i] is 0 and // freqT[i] is not 0 else if (freqS[i] == 0 && freqT[i] != 0) { return "No"; } // If freqS[i] is not freqT[i]*N else if (freqT[i] != 0 && freqS[i] != (freqT[i] * N)) { return "No"; } } // Otherwise, return "Yes" return "Yes"; } // Driver Code public static void Main(string[] args) { string[] arr = { "abc", "abb", "acc" }; string T = "abc"; int N = arr.Length; Console.WriteLine(checkIfPossible(N, arr, T)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to check if it possible// to make all the strings equal to// the string Tfunction checkIfPossible(N, arr, T){ // Stores the frequency of all // the strings in the array arr[] let freqS = new Array(256).fill(0); // Stores the frequency of the // string T let freqT = new Array(256).fill(0); // Iterate over the characters // of the string T for (let ch of T) { freqT[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++; } // Iterate in the range [0, N-1] for (let i = 0; i < N; i++) { // Iterate over the characters // of the string arr[i] for (let ch of arr[i]) { freqS[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++; } } for (let i = 0; i < 256; i++) { // If freqT[i] is 0 and // freqS[i] is not 0 if (freqT[i] == 0 && freqS[i] != 0) { return "No"; } // If freqS[i] is 0 and // freqT[i] is not 0 else if (freqS[i] == 0 && freqT[i] != 0) { return "No"; } // If freqS[i] is not freqT[i]*N else if (freqT[i] != 0 && freqS[i] != (freqT[i] * N)) { return "No"; } } // Otherwise, return "Yes" return "Yes";}// Driver Code let arr = [ "abc", "abb", "acc" ]; let T = "abc"; let N = arr.length; document.write(checkIfPossible(N, arr, T));// This code is contributed by gfgking</script> |
Output:
Yes
Time Complexity: O(N*L + M), Where L is the length of the longest string in the array arr[].
Auxiliary Space: O(26)
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!
