Check if string S can be converted to T by incrementing characters
Given strings S and T. The task is to check if S can be converted to T by performing at most K operations. For the ith operation, select any character in S which has not been selected before, and increment the chosen character i times (i.e., replacing it with the letter i times ahead in the alphabet)
Note: The increment is cyclic (i.e., incrementing ‘z’ by 1 makes the character ‘a’)
Examples:
Input: A = “input”, B = “ouput”, N = 9
Output: True
Explanation: In the 6th operation, we shift ‘i’ 6 times to get ‘o’. And in the 7th operation, we shift ‘n’ to get ‘u’.Input: A = “aab”, B = “bbb”, N = 27
Output: True
Explanation: In the 1st move, we shift the first ‘a’ 1 time to get ‘b’. In the 27th move, we shift the second ‘a’ 27 times to get ‘b’.
An approach using Hashing:
One important thing is to notice that we can only shift a letter once, and we cannot change more than one letter by the same number of shifts (i). In other words, if we shift one letter by 1, no other letters can be shifted by 1. If we need to shift by 1 again, you need to use “wrapping” and shift by 27 (which is 1 + 26).
Follow the steps below to implement the above idea:
- Check if the size of both strings is not equal
- Initialize an array arr[] of size 26. where, arr[i] = x implies that there are x characters in string A that need an increment of i times to match the characters in string B.
- Iterate over the string A.
- Calculate the increment needed to convert A[i] to B[i]
- Calculate the total operation require to shift all the characters that need the same amount of increment.
- If the total operation required is greater than N, return false
- Increment the frequency of shift in array arr by 1
- Finally, return true
Below is the implementation of the above approach:
C++
|
|
Time Complexity: O(size(A))
Auxiliary Space: O(1)
Given strings S and T. The task is to check if S can be converted to T by performing at most K operations. For the ith operation, select any character in S which has not been selected before, and increment the chosen character i times (i.e., replacing it with the letter i times ahead in the alphabet)
Note: The increment is cyclic (i.e., incrementing ‘z’ by 1 makes the character ‘a’)
Examples:
Input: A = “input”, B = “ouput”, N = 9
Output: True
Explanation: In the 6th operation, we shift ‘i’ 6 times to get ‘o’. And in the 7th operation, we shift ‘n’ to get ‘u’.Input: A = “aab”, B = “bbb”, N = 27
Output: True
Explanation: In the 1st move, we shift the first ‘a’ 1 time to get ‘b’. In the 27th move, we shift the second ‘a’ 27 times to get ‘b’.
An approach using Hashing:
One important thing is to notice that we can only shift a letter once, and we cannot change more than one letter by the same number of shifts (i). In other words, if we shift one letter by 1, no other letters can be shifted by 1. If we need to shift by 1 again, you need to use “wrapping” and shift by 27 (which is 1 + 26).
Follow the steps below to implement the above idea:
- Check if the size of both strings is not equal
- Initialize an array arr[] of size 26. where, arr[i] = x implies that there are x characters in string A that need an increment of i times to match the characters in string B.
- Iterate over the string A.
- Calculate the increment needed to convert A[i] to B[i]
- Calculate the total operation require to shift all the characters that need the same amount of increment.
- If the total operation required is greater than N, return false
- Increment the frequency of shift in array arr by 1
- Finally, return true
Below is the implementation of the above approach:
C++
|
|
Time Complexity: O(size(A))
Auxiliary Space: O(1)
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.