String Conversion

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
11 upvotes
Asked in companies
DelhiveryIBMDell Technologies

Problem statement

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'.
For example- 
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 ( Input/output format, Notes, Images )
Input Format: 
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'.
Output Format: 
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.
Constraints: 
1 <= T <= 100
1 <= N <= 5000
1 <= K <= N

Time Limit: 1 sec
Sample Input 1:
1
6 2
cccffc 
eeeegg
Sample output 1:
Yes
Explanation of Sample output 1:
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’).
Sample Input 2:
2
4 3
aaaa
aaaa
3 3
abc
bcd
Sample output 2:
Yes
No
Hint

Try a greedy approach to solve the problem.

Approaches (1)
Greedy Approach

The key observation here is that we can reorder the string in any way after some finite number of swaps. This is helpful as we don’t have to worry about the characters being adjacent when we perform the operation of the second type.

 

To convert string A into B, we first make the frequencies of each character of string equal, then reorder the string using the operation of the first type. 

 

Here is the algorithm:

  1. We will store the frequency of characters of string A and B in two arrays ‘fmap1’ and ‘fmap2’ each of size 26, respectively.
  2. Now we will iterate over the arrays.
    1. If ‘i’ != 0:
      1. We will add the number of characters that are available till i-th index i.e. fmap1[i] += fmap1[i - 1]. This is done because a character at index ‘i - 1’ can be possibly converted to the next character at index ‘i’ by applying operation 2.
    2. If fmap1[i] < fmap2[i]:
      1. We simply return “No” because there are insufficient characters.
    3. fmap1[i] = fmap1[i] - fmap2[i].
      1. fmap1[i] now represents the number of characters that are available for conversion in next iterations.
    4. If fmap1[i] % k != 0
      1. We return “No” because if the number of characters that are available for conversion is not divisible by k then we can’t change all of them into next characters.
  3. Finally, we return “Yes”.
Time Complexity

O(N), where N is the length of the string. 

 

In the worst case, we are iterating the strings only once. Hence, the time complexity is linear.

Space Complexity

O(1), i.e. constant space complexity.

 

We are using arrays of size 26 to store the frequencies. Hence, the space complexity is constant.

Code Solution
(100% EXP penalty)
String Conversion
Full screen
Console