Replace the strings

3.9

22 votes
String manipulation, String Algorithms, Algorithms, String Searching
Problem

You are given two strings S and T that consist of lower case Latin letters and both strings contain single '?'. You need to replace '?' with some lower case Latin letter in both strings not necessarily the same.

After that, you can apply the following operation on S any number of times:

  • Swap any two adjacent characters.

Your task is to determine if it is possible to make S equal to T if you replace '?' with a lower case Latin letter and apply the mentioned operation on S any number of times.

Input format

  • The first line contains the number of test cases TC.
  • The first line of each test case contains the length of string S that is equal to the length of T.
  • The second line of each test case contains the string S.
  • The third line of each test case contains the string T.

Output format

For each test case, print a single line. If possible to make S equal to T, then print 'YES' else 'NO' without quotes.

Constraints

1TC1000

1|S|=|T|100000

The sum of lengths of string in all test cases does not exceed 500000.

Strings S and T contain exactly one '?' and lower case Latin letters.

Sample Input
3
4
abc?
abc?
4
aab?
a?aa
5
aaa?a
bbbb?
Sample Output
YES
YES
NO
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In first sample we can replace '?' in both strings with any character but it must be same.

In second sample we can make S="aaba" and T="abaa" and now we can swap second 'a' and only 'b' in S.

In third sample there is no way to do it.

Editor Image

?