Converts the given string to T, by replacing characters between strings any number of times

Converting a string means we have to make it same as the given string based on the given condition. In this question, we are given an array consisting of string "arr" and string "T" of size "M". Our task is to check if all the strings present in the array can be made identical to the given one by removing any character from the string ( arr[i] ) of the array and inserting that character into any index of another string String T A string of the same array ( arr[j] ). We can do this as many times as we like. Returns "YES" if all strings in the array can be made identical to string 'T', otherwise returns "NO".

Example

Input 1: arr = [ “wxyz”, “wxxy”, “wyzz” ], T = “wxyz”

Output 1: YES

illustrate

One of the possible ways to make all strings in the array identical to the string T is as follows -

• Delete the characters of the string arr[1] ("wxxy") at index 2 and insert them into the string arr[2] ("wyzz") at index 1. Then it looks like: ["wxyz","wxy","wxyzz"]

• Delete the characters of the string arr[2] ("wxyzz") at index 3 and insert them into the string arr[1] ("wxy") at index 3. Then it looks like: ["wxyz","wxyz","wxyz"].

After performing the above steps, we can make all strings in the array the same as the string T. So the answer is "YES".

Input 2: arr = [ “rts”, “rtw”, “rts” ], T = “rts”

Output 2: NO

illustrate

There are 3 strings in the array, 2 of which are the same as string T, but the string with index number 1 is different. It contains different characters that are not part of the string T. It is not possible to make all strings in the array a string T. Therefore, the answer is "NO".

Method: Use Hashmap

We have seen the example of the given string above, let us move to the method -

We have two observations as follows -

• Because we must make all strings in the array the same as string T, so that all characters of each string in the array must appear in string T. In other words, there are no different characters. Otherwise, we cannot meet the conditions.

• After we calculate the frequency of occurrence of characters for all strings in the array, the frequency of occurrence of each character must be equal to the size of array "N".

Based on the above observations, we have two conditions to check.

• The hash map of strings of size array "freqArr" is equal to the hash map "freqT" of string "T". As

freqArr.size() == freqT.size()

• Every character of string T should appear in every string in the array. Each character of string T should have a frequency count of "N" in the array string. as-

freqArr.find(T[i]) == freqArr.end() and 
freqArr[T[i]] != freqT[T[i]]*N.

We can use hashing to solve this problem because we need to calculate the frequency of characters in the array string and string T.

Example

Let us see the code of the above method for better understanding -

// Program to convert all strings to T
#include <bits/stdc++.h>
using namespace std;
string covertStringIntoT( int N, string arr[], string T){
   map< char,int > freqT; //to store the frequency of each character of string T
   int len = T.size(); //getting the size of the string T 
   
   //traverse the string T to store the frequency of the characters
   for( int i=0; i<len; i++){
      freqT[T[i]]++;
   }
   map< char,int > freqArr; //to store the frequency of each chracter of strings 
   
   // of Array.
   //traverse the strings of Array to store the frequency of the characters
   for( int i=0; i<N; i++){
      for(int j=0;j<arr[i].size(); j++){
         freqArr[arr[i][j]]++;
      }
   }
   
   // Check the condition one
   if(freqT.size() != freqArr.size()){
      return "NO";
   }    
   
   //check condition two while trversing the string T
   for( int i=0; i<len; i++){
      if(freqArr.find(T[i]) == freqArr.end() || freqArr[T[i]] != freqT[T[i]]*N ){
         return "NO";
      }
   }
   return "YES";
}
int main() {    
   string T = "wxyz"; // given string
   string arr[] = {"wxyz", "wxyy", "wxzz"}; // given array of strings
   int N = sizeof(arr) / sizeof(arr[0]); //getting the size of the array of string 
   
   // calling the function 'convertStringIntoT' to convert all strings of the 
   
   // array into string T
   string result = covertStringIntoT( N, arr, T);
   if(result == "YES"){
      cout<< result << ", it is possible to make all the strings of the array as string T";
   }
   else{
      cout<< result << ", it is not possible to make all the strings of the array as string T"; 
   }
   return 0;
}

Output

YES, it is possible to make all the strings of the array as string T

Time and space complexity

The time complexity of the above code is O(M N*L)

The space complexity of the above code is O(M)

Where M is the size of the string T, N is the size of the array, and L is the longest string present in the array.

in conclusion

In this tutorial, we implemented a program that converts a given string into a T by replacing characters between the strings as many times as necessary. We implemented a hashing method because we had to store the frequencies. In this method, we mainly check two conditions, if all conditions are met, it means that we are able to convert all the strings in the array into the same string as the string T.

The above is the detailed content of Converts the given string to T, by replacing characters between strings any number of times. For more information, please follow other related articles on the PHP Chinese website!