Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You have given two strings 'A' and ‘B’ of length ‘N’ each which only consists of lowercase English letters. You have also given an integer ‘K’.

Your task is to determine if it is possible to convert string ‘A’ into ‘B’ after performing two types of operations on it:

```
1. Choose an index i (1 <= i <= N - 1) and swap A[i] and A[i+1].
2. Choose an index i (1 <= i <= N - K + 1) and if A[i], A[i+1],. . . . , A[i+K-1] all are equal to some character x (x != ‘z’), then you can replace each one with the next character (x + 1) , i.e. ‘a’ is replaced by ‘b’, ‘b’ is replaced by ‘c’ and so on.
```

Note:

```
You are allowed to perform any operation any number of times(possibly zero) only on string 'A'.
```

```
If the given strings are A = ‘xbbx’ and B = ‘xddx’ and K is given as 2. Then it is possible to convert string A into B by applying the second operation two times on index 2 (1 based indexing).
```

Detailed explanation

```
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains two space-separated integers ‘N’ and ‘K’, respectively.
The second line of each test case contains the string ‘A'.
The third line of each test case contains the string ‘B'.
```

```
The only line of output contains a string “Yes” if it is possible to convert string A into B, else “No”.
Print the output of each test case in a separate line.
```

Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= N <= 5000
1 <= K <= N
Time Limit: 1 sec
```

```
1
6 2
cccffc
eeeegg
```

```
Yes
```

```
It is possible to convert the string ‘cccffc’ into ‘eeeegg’. Firstly, apply operation 1 on index 5 (‘cccfcf’). Then operation 1 on index 4 (‘ccccff’). Finally, apply operation 2 on index 5 (‘ccccgg’).
```

```
2
4 3
aaaa
aaaa
3 3
abc
bcd
```

```
Yes
No
```