Make the strings equal

3.5

17 votes
String Algorithms, Algorithms, String, String Searching
Problem

You are given two strings S and T consisting of lower case Latin letters. Your task is to determine if you can make S equal to T using the following operation:

  • Swap any two adjacent characters in S and also swap any two adjacent characters in T.

Note: It is necessary to swap both the strings and it is not optional if you are applying operation.

Input format

  • The first line contains an integer T denoting the number of test cases.
  • The first line of each test case contains an integer denoting the length of S.
  • The second line of each test case contain string S.
  • The third line of each test case contain string T.

Output format

Print T lines. For each test case:

  • Print a single line 'YES' if you can make S equal to T else 'NO'.

Constraints

1T20000

1|S|=|T|200000

The sum of |S| over all test cases is less than or equal to 5×105.

Sample Input
3
4
abcd
dacb
4
aabb
bbaa
2
ab
ba
Sample Output
YES
YES
NO
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

First Sample:

  • swap a,b in S and d,a in T. S="bacd" T="adcb"
  • swap c,d in S and d,c in T  S="badc" T="acdb"
  • swap a,b in S and b,d in T S="abdc"  T="acbd"
  • swap d,c in S and b,c in T S="abcd"   T="abcd".

Similarly follow other samples

Editor Image

?