STRING DA MUQABLA

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
4 upvotes
Asked in companies
Tata Consultancy Services (TCS)Salesforce

Problem statement

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.

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.

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

Sample Input 1 :

2
bab cbb
badabb cba

Sample Output 1 :

2
3

Explanation of Sample Input 1 :

Test Case 1 :
For the first test case, given ‘STR1 = bab’ and ‘STR2 = cbb’ 
We can change ‘STR2 = ccc’ by changing both ‘b’ in ‘STR2’ to ‘c’ in two steps.
We can change ‘STR1 = aaa’ and ‘STR2 = bbb’ in three steps.
We can change ‘STR1 = bbb’ and ‘STR2 = bbb’ in two steps.
So we return ‘2’ as it is the minimum number of steps to satisfy one of the given rules.

Test Case 2 :
For this test case, given ‘STR1 = badabb’ and ‘STR2 = cba’
We can change ‘STR2 = eee’ and satisfy the first rule so the minimum number of steps required is ‘3’.

Sample Input 2 :

1
ab bb

Sample Output 2 :

1

Explanation of Sample Input 2 :

Test Case 1 : 
For this test case, we can change ‘STR1 = aa’ so we return ‘1’ as the answer.
Hint

Can you check all the given rules and compare their results?

Approaches (1)
Iterative Approach

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 in each iteration store, the minimum count obtained.
  • 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
Time Complexity

O(L1 + L2), where L1 represents the length of ‘STR1’ and L2 represents the length of ‘STR2’.

 

As we are running a constant loop from ‘a’ to ‘z’ and for checking both the rules we are running a loop for both the length of the string so overall complexity becomes equal to O(L1 + L2).

Space Complexity

O(1).

 

As no extra space is required.

Code Solution
(100% EXP penalty)
STRING DA MUQABLA
Full screen
Console