Last Updated: 25 Apr, 2021
STRING DA MUQABLA
Moderate
Asked in company
One day ninja is thinking of a competition between two strings wherein each round two strings take part and there are some rules of that competition if the strings are able to tell that the minimum numbers of characters they need to change to satisfy at least one of the rules they will be declared as the winner.
Rules for the competition are as follows :
The character of every string of ‘STR1’ is strictly less than every character of every string of ‘STR2’ and vice versa.
‘STR1’ and ‘STR2’ only differ in one distinct character.
So your task is to find the minimum numbers of characters we need to change to satisfy and of the given rule.
Input Format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains two strings ‘STR1’ and ‘STR2’, representing both the strings.
Output Format :
For each test case, print a single line as the minimum number of characters needed to be changed.
The output of each test case will be printed 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 <= 5
1 <= |STR1|, |STR2| <= 5000
Where ‘T’ represents the number of test cases and ‘STR1’ represents the given first string and ‘STR2’ represents the given second string.
Time Limit: 1 second
Approaches
The idea here is to count the number of steps required to make all characters of ‘STR2’ strictly greater than ‘STR1’ and vice versa and also to count the number of steps required to satisfy rule ‘2’ i.e ‘STR1’ and ‘STR2’ only differ by one distinct character and after that, we return the minimum number of steps required from both the condition.
Algorithm:
- Firstly we count the number of steps required to make all the characters of ‘STR2’ greater than ‘STR1’.
- For this, we run a loop where ‘i’ starts from ‘a’ and run upto ‘z’ as we want to select a breakpoint ‘i’ so that we make all characters of ‘STR1’ <= ‘i’ and ‘STR2’ > ‘i’.
- Now we run another loop where ‘K’ starts from ‘STR1[0] up to the length of the ‘STR1’.
- In each iteration, we count the number of characters in ‘STR1’ > ‘i’ as they need to change.
- Now we run another loop where ‘L’ starts from ‘STR2[0] up to the length of the ‘STR2’.
- In each iteration, we count the number of characters in ‘STR2’ < ‘i’ as they need to change.
- Now we run another loop where ‘K’ starts from ‘STR1[0] up to the length of the ‘STR1’.
- Now in each iteration store, the minimum count obtained.
- For this, we run a loop where ‘i’ starts from ‘a’ and run upto ‘z’ as we want to select a breakpoint ‘i’ so that we make all characters of ‘STR1’ <= ‘i’ and ‘STR2’ > ‘i’.
- Now repeat the above steps by considering ‘STR2’ in place of ‘STR1’ and ‘STR1’ in place of ‘STR2’ respectively.
- Now for obtaining the number of steps required to satisfy rule 2:
- We run a loop where ‘i’ starts from ‘a’ and run upto ‘z’ as we want to select a breakpoint and make use of the condition that all characters are changed to ‘i’ and now we obtained a count of how many characters of ‘STR1’ is not equal to ‘i’.
- In the same way, we obtained the count of how many characters of ‘STR2’ is not equal to ‘i’.
- In each iteration, we store the minimum number of counts obtained.
- Now in the end we return the minimum value obtained from all of our procedures