Equalizing Two Strings (Codeforces 1256F)
Tags: Others, strings

You are given two strings $$$s$$$ and $$$t$$$ both of length $$$n$$$ and both consisting of lowercase Latin letters.In one move, you can choose any length $$$len$$$ from $$$1$$$ to $$$n$$$ and perform the following operation:   Choose any contiguous substring of the string $$$s$$$ of length $$$len$$$ and reverse it;  at the same time choose any contiguous substring of the string $$$t$$$ of length $$$len$$$ and reverse it as well. Note that during one move you reverse exactly one substring of the string $$$s$$$ and exactly one substring of the string $$$t$$$.Also note that borders of substrings you reverse in $$$s$$$ and in $$$t$$$ can be different, the only restriction is that you reverse the substrings of equal length. For example, if $$$len=3$$$ and $$$n=5$$$, you can reverse $$$s[1 \dots 3]$$$ and $$$t[3 \dots 5]$$$, $$$s[2 \dots 4]$$$ and $$$t[2 \dots 4]$$$, but not $$$s[1 \dots 3]$$$ and $$$t[1 \dots 2]$$$.Your task is to say if it is possible to make strings $$$s$$$ and $$$t$$$ equal after some (possibly, empty) sequence of moves.You have to answer $$$q$$$ independent test cases.

Input: The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 10^4$$$) — the number of test cases. Then $$$q$$$ test cases follow.The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$s$$$ and $$$t$$$.The second line of the test case contains one string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.The third line of the test case contains one string $$$t$$$ consisting of $$$n$$$ lowercase Latin letters.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output: For each test case, print the answer on it — "YES" (without quotes) if it is possible to make strings $$$s$$$ and $$$t$$$ equal after some (possibly, empty) sequence of moves and "NO" otherwise.


Sample Inputs:
4
4
abcd
abdc
5
ababa
baaba
4
asdf
asdg
4
abcd
badc

Sample Outputs:
NO
YES
NO
YES

Solution (Python):
from collections import *
g = input
q = len
m = range
f = lambda s: (Counter(s), q(set(s)) == q(s) and sum((s[i] > s[j] for i in m(q(s)) for j in m(i, q(s)))) & 1)
for _ in m(int(g())):
    (n, s, t) = (g(), g(), g())
    print('YNEOS'[f(s) != f(t)::2])

Solution (Python):
import sys

def minp():
    return sys.stdin.readline().strip()

def mint():
    return int(minp())

def mints():
    return map(int, minp().split())

def solve():
    n = mint()
    s = list(minp())
    t = list(minp())
    if sorted(t) != sorted(s):
        print('NO')
        return
    for i in range(26):
        if s.count(chr(ord('a') + i)) > 1:
            print('YES')
            return
    r = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if t.index(s[i]) > t.index(s[j]):
                r += 1
    print(['NO', 'YES'][r % 2 == 0])
for i in range(mint()):
    solve()

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    (s1, s2) = (input(), input())
    (a1, a2) = ([0] * 26, [0] * 26)
    for v in map(ord, s1):
        a1[v - 97] += 1
    for v in map(ord, s2):
        a2[v - 97] += 1
    if a1 != a2:
        print('NO')
        continue
    if max(a1) > 1:
        print('YES')
        continue
    inv1 = sum((c1 > c2 for (i, c1) in enumerate(s1) for c2 in s1[i + 1:]))
    inv2 = sum((c1 > c2 for (i, c1) in enumerate(s2) for c2 in s2[i + 1:]))
    print('YES' if inv1 % 2 == inv2 % 2 else 'NO')