Determine if Two Strings Are Close

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
7 upvotes
Asked in company
Walmart

Problem statement

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?.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
abcd dcba 
aaabbcc aabcccb
Sample Output 1 :
true
true
Explanation of sample input 1 :
In the first test case,
First, swap characters ‘a’ and ‘d’ of string ‘STR1’ after this ‘STR1’ is “dbca”.
Then swap characters ‘b’ and ‘c’ of string ‘STR1’ after this ‘STR1’ is “dcba”.
Now both the strings are equal.

In the second test case,
First, change every occurrence of ‘a’ and ‘c’ of string ‘STR1’ into each other. After this ‘STR1’ is “cccbbaa”.
Then swap characters present at index (0, 5) then (1, 6) then (2,3) After that ‘STR1’ is 
“aabcbcc”. Now swap characters present at index (4, 6) after this ‘STR1’ is “aabcccb”.
Now both the strings are equal.
Sample Input 2 :
2
ba baa
aabbbc aabbss
Sample Output 2 :
false
false
Explanation for sample input 2 :
In the first test case, the number of characters in both the strings is different hence we can not make these strings equal.

In the second test case, the character ‘c’ is present in ‘STR1’ but not present in ‘STR2’ hence we can not make these strings equal.
Hint

Can you think of storing the frequency of characters of both the strings?

Approaches (1)
Greedy Approach

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:

 

  1. If the length of both the strings ‘STR1’ and ‘STR2’ are not equal:
    • Return false.
  2. Declare two arrays/vectors ‘freq1’ and ‘freq2’ each of length 26 as we have discussed above.
  3. Iterate through both the strings ‘STR1’ and ‘STR2’ and store frequency of characters into ‘freq1’ and ‘freq2’ respectively.
  4. Sort both the arrays/vectors  ‘freq1’ and ‘freq2’.
  5. Run a loop ‘i’ = 0 to ‘26’:
    • If ‘freq1[i]’ is not equal to ‘freq2[i]’.
      • Return false.
  6. Finally, return true.
Time Complexity

O(max(|STR1|, |STR2|), where |’STR1’| and |‘STR2’| denotes the length of the string ‘STR1’ and ‘STR2’.

 

First, we are Iterating through both the strings ‘STR1’ and ‘STR2’ for storing the frequency of their characters. Then we are sorting both frequency arrays/vectors each of constant size i.e 26 and so it takes constant time for sorting. Hence the overall time complexity is O(max(|STR1|, |STR2|).

Space Complexity

O(1).

 

We are storing the frequency of each character in an array/vector but we know that the strings are only composed of lowercase English alphabets (26 in number) and so we are only using constant extra space. Hence, the overall space complexity is constant.

Code Solution
(100% EXP penalty)
Determine if Two Strings Are Close
Full screen
Console