Codeforces Round #685 (Div. 2) C. String Equality（简单思维）

本文主要是介绍Codeforces Round #685 (Div. 2) C. String Equality（简单思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://codeforc.es/contest/1451/problem/C

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≤i≤n−1) and swap ai and ai+1, or
choose an index i (1≤i≤n−k+1) and if ai,ai+1,…,ai+k−1 are all equal to some character c (c≠ ‘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
The first line contains a single integer t (1≤t≤105) — 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≤n≤106) and k (1≤k≤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 106.

Output
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).

Example

input

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

output

No
Yes
No
Yes

题意

给出两个同样长度的字符串 a ， b 。可以对 a 做如下操作：1、将两个相邻字符交换；2、将连续 k 个相同字符都变为他们的下一个（ a 变为 b ， b 变为 c…… z 不能变）。问能否将 a 变为 b 。

分析

因为操作 1 ，我们可以发现最终字符的顺序我们是不用管的，只需要将 a 变成各字符数和 b 都对应相等就可以了。
我们从 ‘a’ 字符开始遍历 26 个字母，如果 b 中有，就抵消掉，如果抵消过后还有剩余字数，那么肯定要都转化成下一个字母，如果转化不完，说明 a 必定不能转化为 b ，如果某种字母不够，那么说明也是不能的。
注意判断是否转化了 ‘z’ 。

代码

#include<bits/stdc++.h>
using namespace std;int t;
int n,k;
int a[2][27];
char s[1000007];int main()
{scanf("%d",&t);while(t--){memset(a, 0, sizeof(a));scanf("%d%d",&n,&k);scanf("%s",s);for(int i=0;i<n;i++)a[0][s[i] - 'a']++;scanf("%s",s);for(int i=0;i<n;i++)a[1][s[i] - 'a']++;int flag = 1;for(int i=0;i<26;i++){if(a[0][i] < a[1][i]){flag = 0;break;}int minn = min(a[0][i], a[1][i]);a[0][i] -= minn;a[1][i] -= minn;if(a[0][i] % k != 0){flag = 0;break;}a[0][i + 1] += a[0][i];a[0][i] = 0;}if(a[0][26] > 0) flag = 0;//如果有则说明转化了z，但z是不能转化的 if(flag == 1) printf("Yes\n");else printf("No\n");}return 0;
}