String Equality
Contest: Codeforces Round 685 (Div. 2)
Difficulty rating: 1400
Tags: dp, greedy, hashing, implementation, strings

Ashish has two strings $$$a$$$ and $$$b$$$, each of length $$$n$$$, and an integer $$$k$$$. The strings only contain lowercase English letters.

He wants to convert string $$$a$$$ into string $$$b$$$ by performing some (possibly zero) operations on $$$a$$$.

In one move, he can either

- choose an index $$$i$$$ ($$$1 \leq i\leq n-1$$$) and swap $$$a_i$$$ and $$$a_{i+1}$$$, or
- choose an index $$$i$$$ ($$$1 \leq i \leq n-k+1$$$) and if $$$a_i, a_{i+1}, \ldots, a_{i+k-1}$$$ are all equal to some character $$$c$$$ ($$$c \neq$$$ 'z'), replace each one with the next character $$$(c+1)$$$, that is, 'a' is replaced by 'b', 'b' is replaced by 'c' and so on.

Note that he can perform any number of operations, and the operations can only be performed on string $$$a$$$.

Help Ashish determine if it is possible to convert string $$$a$$$ into $$$b$$$ after performing some (possibly zero) operations on it.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of each test case is as follows.

The first line of each test case contains two integers $$$n$$$ ($$$2 \leq n \leq 10^6$$$) and $$$k$$$ ($$$1 \leq k \leq n$$$).

The second line of each test case contains the string $$$a$$$ of length $$$n$$$ consisting of lowercase English letters.

The third line of each test case contains the string $$$b$$$ of length $$$n$$$ consisting of lowercase English letters.

It is guaranteed that the sum of values $$$n$$$ among all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, print "Yes" if Ashish can convert $$$a$$$ into $$$b$$$ after some moves, else print "No".

You may print the letters of the answer in any case (upper or lower).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case it can be shown that it is impossible to convert $$$a$$$ into $$$b$$$.

In the second test case,

"abba" $$$\xrightarrow{\text{inc}}$$$ "acca" $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ "azza".

Here "swap" denotes an operation of the first type, and "inc" denotes an operation of the second type.

In the fourth test case,

"aaabba" $$$\xrightarrow{\text{swap}}$$$ "aaabab" $$$\xrightarrow{\text{swap}}$$$ "aaaabb" $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ "ddaabb" $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ "ddddbb" $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ "ddddcc".

Example input:
4
3 3
abc
bcd
4 2
abba
azza
2 1
zz
aa
6 2
aaabba
ddddcc

Example output:
No
Yes
No
Yes

Editorial:
Key Idea:
For the answer to be YES, the frequencies of each character of the alphabet must match after performing some sequence of operations. Let $$$freq_{i, a}$$$ and $$$freq_{i, b}$$$ be the frequencies of the $$$i$$$-th character of the alphabet in strings $$$a$$$ and $$$b$$$ respectively. For each $$$i$$$ starting from "a", we keep exactly $$$freq_{i, b}$$$ of the occurrences and try to to convert the rest into the next character. If at any step, this is not possible, the answer is NO.
Solution:
Consider operations of the first type. It can be shown that after some finite sequence of swaps, we can reorder the string in any way we like. This is helpful because we do not have to worry about the characters being adjacent when we perform an operation of the second type (we can always reorder the string to allow it). In other words, only frequency of the characters matter.
To convert string $$$a$$$ into string $$$b$$$, we first make the frequencies of each character of the alphabet equal, then reorder the string using operations of the first type. The former can be done as described above. If for any $$$i$$$, there are an insufficient number of occurrences ($$$freq_{i, a} \lt freq_{i, b}$$$) or the remaining occurrences cannot all be converted into the next character, i.e. $$$(freq_{i, a} - freq_{i, b})$$$ is not a multiple of $$$k$$$, the answer is NO. Otherwise, the answer is YES.
Time complexity: $$$O(n)$$$