Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 7 Jul, 2021

Ninja

```
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.
```

```
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.
```

```
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.
```

```
You are not required to print anything; it has already been taken care of. Just implement the function.
```

```
1 <= T <= 50
1 <= N <= 10^4
Time Limit: 1 sec.
```

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).

- Make two variables ‘MN’ and ‘MX’.
- Iterate on the length of string ‘A’ from 0 to ‘N’-1.
- Rotate string ‘A’ to the left by 1.

- Then again, run 2 loops and calculate the difference and store it in ‘DIFF’.
- Update ‘MN’ with the minimum of ‘MN’ and ‘DIFF’ and ‘MX’ with the maximum of ‘MX’ and ‘DIFF’.
- Make an array/list ‘ANS’ and push ‘MN’ and ‘MX’ variables in it.
- Return the ‘ANS’.

Note that there are only 26 different characters. We will use this fact and calculate each character's contribution in the difference of the strings for each rotation of string ‘A’. We will do the following for character each character ‘CH’ (ranging from ′a′ to ′z′).

Let us define two arrays ‘X’ and ‘Y’ each of length ‘N’ where:

X[i] = 1 if A[i] == CH and 0 otherwise.

Y[i] = |B[i] − CH| + |C[i] − CH|.

Lets us also define two polynomials P1=∑X[I] * (X ^ I) and P2 = ∑Y[I] * (X ^ (N − I)). Consider the polynomial P = P1 * P2. The coefficient of X ^ N is ∑X[i] * Y[i] is exactly the contribution of ‘CH’ in the difference of the three strings if the string 'A' is not rotated. Similarly, it is easy to observe that for all rotations ‘I’ of string a from 1 to ‘N’ − 1, the contribution of character ‘CH’ is the sum of coefficients of X ^ (N − I) and X ^ (2 * N − I).

We will use FFT to multiply two polynomials of degree ‘N’ in O(N * logN).

- Make an array/list ‘ANS’
**N’**initialize it with 0. - Run a loop on characters from 'a' to 'z'
- Make two arrays ‘V
**1’**and 'V**2'**of size ‘**N’**. - Inside loop iterate over the string and update the values V1
**[I]**and V2**[I]**. - Call multiply function and multiply the polynomial coefficients by arrays ‘V
**1’**and**‘V2’**and store it in array/list 'RES'. - Multiply function will take two arrays and returned the polynomial after multiplying the values of array coefficients.
- Make two variables ‘MN’ and ‘MX’ and update the values with a minimum of ‘RES’ array and maximum of ‘RES’ array respectively.
- Make an array/list ‘ANS’ and push ‘MN’ and ‘MX’ variables in it.
- Return the ‘ANS’.