Alice and her love for Strings.

Easy
0/40
Average time to solve is 10m
profile
Contributed by
6 upvotes
Asked in companies
AdobeMeeshoOkcredit

Problem statement

Alice loves string and Bob being her best friend wants to gift a beautiful string to Alice on her birthday. He knows that Alice loves her childhood string ‘A’ and would love to get a new string similar to the string ‘A’.

Somehow Bob convinced one of his friends to send him a random string ‘B’. Now Bob will have to change the random string ‘B’ to make it equal to string ‘A’ so that he can gift this string to Alice on her birthday. But changing the string is a very tedious process. He can change one character of the string to any other character in a single step.

Now he wonders if it is even possible to change the string ‘B’ to string ‘A’ by using at most ‘K’ steps? Can you help Bob figure out if it is even possible to do so under given constraints?

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. Then the test cases follow.

The first line of each test case contains the integer ‘K’, The maximum number of changes that are allowed to be made.

The second line of each test case contains the string ‘A’, The string that Alice loves. ‘A’ contains all lowercase letters.

The third line of each test case contains the random string ‘B’ that Bob got from his friend. ‘B’ contains all lowercase letters.
Output Format: 
For each test case, Return True if it is possible to change string ‘B’ to string ‘A’ under given constraints else return False.

Print the output of each test case in a new line.
Constraints: 
1 <= T <= 5
1 <= k <= 10^5
1 <= |A| <= 10^5
1 <= |B| <= 10^5

Time Limit = 1 sec
Sample Input 1:
2
4
coding
ninjaa
3
coding
ninjaa
Sample Output 1:
Yes
No
Explanation for Sample Input 1:
The minimum number of step required to change ninjaa to coding is 4 by changing 
n -> c, j -> o, a -> d, a-> g. 
Hence, in the first testcase where k = 4, it is possible to change string ‘B’ to ‘A’ and not possible in the second testcase.
Sample Input 2:
2
5
aaabbccdddd
aabbccddsss
3

aaabbb aabb

Sample Output 2:
Yes
No
Hint

Only the frequency of each character is important.

Approaches (1)
Using Frequency Array

The approach is pretty simple. First, generate the freq of each character for both string A and string B. Now for every character in string B, if the frequency of this character is more in string B as compared to string A, then we forcefully need to change some of the characters preferably their difference to some other character in order to make it equal to string B. count the sum of changes for each character and if it is less than or equal to K then it is possible to change string B to A under given constraints else not.


 

The only base case to be considered is if the length of each string is not equal then it is impossible to make them equal.



 

Algorithm: 

  • If the length of strings are different then return false;
  • Generate separate frequency arrays for both strings.
  • Initialize changes = 0.
  • Run a loop for each character from ‘a’ to ‘z’:
    • Increment changes by max(0, freq_B[currchar] - freq_A[currchar]).
  • Return changes <= k.
Time Complexity

O(N), where ‘N’ is the size of the larger length string.


 

Since we are traversing both the strings to generate frequency arrays.


 

Space Complexity

O(1)

We are just using extra O(26) space which is constant itself.


 

Code Solution
(100% EXP penalty)
Alice and her love for Strings.
Full screen
Console