【Codeforces 1451 C】String Equality，贪心，判断能否构造成字符串

problem

C. String Equality
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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
inputCopy
4
3 3
abc
bcd
4 2
abba
azza
2 1
zz
aa
6 2
aaabba
ddddcc
outputCopy
No
Yes
No
Yes
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” −→inc “acca” −→inc … −→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” −→−−swap “aaabab” −→−−swap “aaaabb” −→inc … −→inc “ddaabb” −→inc … −→inc “ddddbb” −→inc … −→inc “ddddcc”.

solution

/*
题意：
+ 给定两个字符串ab和k，判断a能否通过交换相邻字母或者替换k个相同字母ch为ch+1而变成b。
思路：
+ 可以无限交换所以顺序无关，直接排序或统计
+ 统计个数，如果'a'不够肯定没法，否则就按k替换成更大的。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
int aa[26], bb[26];
int main(){
	ios::sync_with_stdio(false);
	int T;  cin>>T;
	while(T--){
		int n, k;  cin>>n>>k;
		string a, b;  cin>>a>>b;
		memset(aa,0,sizeof(aa));
		memset(bb,0,sizeof(bb));
		for(int i = 0; i < n; i++)aa[a[i]-'a']++;
		for(int i = 0; i < n; i++)bb[b[i]-'a']++;
		int ok = 1;
		for(int i = 0; i < 26; i++){
			if(aa[i]==bb[i])continue;
			else if(aa[i]>bb[i]){
				int kk = (aa[i]-bb[i])/k;
				aa[i+1] += kk*k;
			}else{
				ok = 0; break;
			}
		}
		if(ok==1)cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/113480863