Last Updated: 15 Nov, 2021
Alice and her love for Strings.
Easy
Asked in companies
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?
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
Approaches
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.