Last Updated: 25 Nov, 2020
Amazing Strings
Easy
Asked in companies
Shrey has just arrived in the city. When he entered the city, he was given two strings. Now, after arriving at his college, his professor gave him an extra string. To check his intelligence, his professor told him to check if the third string given to him has all the characters of the first and second strings in any order. Help Shrey before his professor scolds him. He has to answer “YES” if all characters are present else “NO”.
Example: ‘HELLO’ and ‘SHREY’ are two initial strings, and his professor gave him ’HLOHEELSRY’. So, here all the characters are present, so he has to say “YES”.
Note: The strings contain only uppercase Latin characters.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains three strings, and the first two strings, i.e. ‘FIRST’ and ‘SECOND’ are the strings which he was given at the beginning, and the third string is ‘THIRD’, which was given by the professor.
Output Format:
For each test case, you have to return “YES” if all characters are present in the third string of the first and second strings; else, return “NO”.
Print the output of each test case in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 10^2
1 <= |FIRST|, |SECOND|, |THIRD| <= 10^5
Time Limit: 1 sec
Approaches
The basic idea of this approach is that we will initially iterate through both the strings (‘FIRST’ and ‘SECOND’) and for all the characters present in them we will try to remove the same character from ‘THIRD’. So, after every iteration, one character from string ‘THIRD’ will be removed and if the letter is not found in between then we will return “NO”. At last, we will check that if string ‘THIRD’ becomes empty that means that all characters match and will return “YES” or else will return “NO” as few extra characters are present in string ‘THIRD’.
Here is the algorithm:
- Declaring an array of size equal to length of the string ‘THIRD’ and assigning them value as 0.
- Iterating from starting of string ‘FIRST’ to ending of it.
- Declare a temporary variable named ‘TEMP’ to keep track of the current character and initialize it with 0.
- Check for the first occurrence of that particular character in the string ‘THIRD’.
- If the character matches the current character of ‘FIRST’ and also the current character is not visited them we got the corresponding character for the current character.
- Mark current index as visited and change of ‘TEMP’ variable to 1 as it indicates that corresponding character is found and break the loop.
- If the character matches the current character of ‘FIRST’ and also the current character is not visited them we got the corresponding character for the current character.
- If ‘TEMP’ is still 0 that means that the corresponding character is not found and so, return “NO”.
- Iterating from starting of string ‘SECOND’ to ending of it.
- Declare a temporary variable named ‘TEMP’ to keep track of the current character and initialize it with 0.
- Check for the first occurrence of that particular character in the string ‘THIRD’.
- If the character matches the current character of ‘SECOND’ and also the current character is not visited them we got the corresponding character for the current character.
- Mark current index as visited and change of ‘TEMP’ variable to 1 as it indicates that corresponding character is found and break the loop.
- If the character matches the current character of ‘SECOND’ and also the current character is not visited them we got the corresponding character for the current character.
- If ‘TEMP’ is still 0 that means that the corresponding character is not found and so, return “NO”.
- After iterating both the strings ‘FIRST’ and ‘SECOND’, we will check that if any character is still unvisited or not.
- If any character is found not visited then we will return “NO”, else “YES”.
The basic idea of this approach is to count the number of total occurrences of each letter in strings ‘FIRST’, ‘SECOND’ and ‘THIRD’. Then, we will check for all the letters present, whether the sum of occurrences of the first two strings is the same as the third or not. If all the occurrences of all letters are the same then at last we will return “YES” or else we will return “NO”.
Here is the algorithm:
- Declare three temporary arrays as ‘S1’, ‘S2’ and ‘S3’ of size 26 and assign them values 0 which will point to the number of occurrences of that particular ASCII valued letter of the strings ‘FIRST’, ‘SECOND’ and ‘THIRD’.
- Iterating from starting of string ‘FIRST’ to ending of it.
- Incrementing the value of the index having ASCII value same as the current character in ‘S1’.
- Iterating from starting of string ‘SECOND’ to ending of it.
- Incrementing the value of the index having ASCII value same as the current character in ‘S2’.
- Iterating from starting of string ‘THIRD’ to ending of it.
- Increment the value of the index having ASCII value same as the current character in ‘S3’.
- Run a loop for ‘i’ = 0 to 255 :
- If the sum of ‘S1[i]’ and ‘S2[i]’ equals ‘S3[i]’ then we will continue iterating through the loop.
- Else we will return “NO” as the total number of occurrences of that particular character in the combination of ‘FIRST’ and ‘SECOND’ and of ‘THIRD’ doesn’t match.
- Finally, return “YES”.