Last Updated: 14 Apr, 2021
Determine if Two Strings Are Close
Moderate
Asked in company
Sagar and Naresh are friends. Sagar loves to play with strings. He gave a challenge to Naresh. Sagar gave him two strings, ‘STR1’ and ‘STR2’, and asked to make both the strings equal by using only the below-given operations.
1) He can swap any two characters of a string.
For example, “coding” -> “cgdino” i.e., swap ‘o’ with ‘g’.
2) He can change every occurrence of two existing characters into each other.
For example, “aababcc” -> “ccbcbaa” i.e., change all occurrences of ‘a’ into ‘c’ and ‘c’ into ‘a’.
Note: Naresh can use these operations on either of the string and any number of times.
Can you help Naresh to do this task?.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain two single space-separated strings ‘STR1’ and ‘STR2’ as mentioned above.
Output Format:
For each test case, print true if Naresh can make both the given strings equal. Otherwise, print false.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 50
1 <= |’STR1’|, |‘STR2’| <= 100000
‘STR1’ and‘STR2’ will only be composed of lowercase English alphabets.
Where ‘T’ is the number of test cases and |’STR1’| and |‘STR2’| are the lengths of strings ‘STR1’ and ‘STR2’.
Time limit: 1 sec
Approaches
As we know we can swap any number of times. Hence ordering of characters does not matter. First, store the frequency of characters of both the strings in arrays/vectors ‘freq1’ and ‘freq2’. If there are some characters that are present in ‘STR1’ but not in ‘STR2’ and vice versa, then return false. Now we know both strings contain similar characters.
We know we can change every occurrence of two existing characters into each other.
So sort both the frequency arrays/vectors and check if ‘freq1[i]’ is equal to ‘freq2[i]’ or not.
The steps are as follows:
- If the length of both the strings ‘STR1’ and ‘STR2’ are not equal:
- Return false.
- Declare two arrays/vectors ‘freq1’ and ‘freq2’ each of length 26 as we have discussed above.
- Iterate through both the strings ‘STR1’ and ‘STR2’ and store frequency of characters into ‘freq1’ and ‘freq2’ respectively.
- Sort both the arrays/vectors ‘freq1’ and ‘freq2’.
- Run a loop ‘i’ = 0 to ‘26’:
- If ‘freq1[i]’ is not equal to ‘freq2[i]’.
- Return false.
- If ‘freq1[i]’ is not equal to ‘freq2[i]’.
- Finally, return true.