Replace the strings

3.9

22 votes
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

\(1 \leq TC \leq 1000\)

\(1 \leq |S|=|T| \leq 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.

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

?