Similar Strings

Ninja
0/200
Average time to solve is 70m
profile
Contributed by
6 upvotes
Asked in companies
LinkedInHCL TechnologiesCodenation

Problem statement

You are given three strings, 'A', 'B', and 'C', each of length 'N' consisting of lower case alphabets. The difference between the three strings is defined as ∑|A[i] − B[i]| + |A[i] − C[i]| where |A[i] − B[i]| and |A[i] − C[i]| are the absolute differences between ASCII values of the characters at the position i in strings 'A', 'B' and 'A' ,'C' respectively. You are allowed to rotate the string 'A' cyclically. There are a total of 'N' possible rotations of a string of length 'N'.

Your task is to return the maximum and minimum difference of the three strings for all the possible rotations of string a.

For Example: 
If the value of 'N' is 2, 'A' is "ab" , 'B' is "aa" and 'C' is "bb".
Then the answer for this input is
min = 2 
max = 2

Because current difference is 1 + 1 = 2
After one rotation difference will be 1 + 1 = 2
Hence, the minimum and the maximum answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow.

First line: Single integer 'N' (the length of the three strings)

Following three lines: Strings 'A, 'B', and 'C', respectively.
Output Format: 
For each test case, Print two space-separated integers denoting the maximum and minimum difference of the three strings for all possible rotations of string a.

Output for each test case will be printed in a separate line.
Note 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 50
1 <= N <= 10^4

Time Limit: 1 sec.
Sample Input 1:
2
3
abc
aaa
bba
2
ab
bb
ab
Sample Output 1:
6 4
3 1
Explanation For Sample Input 1:
For the first test case, there will be 3 possible rotations for the 
string 'A'. in the first rotation, it will make the difference of 6 in 
the second rotation, the difference will be 4 and in the third 
rotation, the difference will be 6.

Hence max answer is 6, and the min is 4 here.

Similarly, in the second test case, the max answer will be 3 and 
the min will be 1.
Sample Input 2:
2
2
ab
bb
ac
2
ab
bb
ac
Sample Output 2:
4 2
3 3
Hint

Try to iterate on all possible rotations of the string.

Approaches (2)
Brute Force

We need to find the difference of the three strings for all possible rotations of string ‘A’ and output the maximum and minimum value. This can be done natively by calculating the difference for each process in O(N). The complexity of this approach is O(N^2).

 

Algorithm

 

  1. Make two variables ‘MN’ and ‘MX’.
  2. Iterate on the length of string ‘A’ from 0 to ‘N’-1.
    • Rotate string ‘A’ to the left by 1.
  3. Then again, run 2 loops and calculate the difference and store it in ‘DIFF’.
  4. Update ‘MN’ with the minimum of ‘MN’ and ‘DIFF’ and ‘MX’ with the maximum of ‘MX’ and ‘DIFF’.
  5. Make an array/list ‘ANS’ and push ‘MN’ and ‘MX’ variables in it.
  6. Return the ‘ANS’.
Time Complexity

O(N^2), Where ‘N’ is the size of the strings.

 

Because we are iterating over the string of size ‘N’ and inside each iteration, we are again iterating over the string of size ‘N’.

Space Complexity

O(1)

 

Because here we are only using constant extra space. 

Code Solution
(100% EXP penalty)
Similar Strings
Full screen
Console