Similar Strings

3.7

3 votes
Algorithms, Convolution, Fast Fourier transform, Medium
Problem

You are given three strings a, b and c  each of length n consisting of lower case English letters. The difference between the three strings is defined as ni=1 |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. However, the string a can be rotated cyclically (for example the rotations of the string xyz are xyz,zxy,yzx). There are a total of n possible rotations of a string of length n.

Print the maximum and minimum difference of the three strings for all the possible rotations of the string a.

Input format

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

Next three lines: Strings a,b and c respectively

Output Format:

Print two space-separated integers: the maximum and minimum difference of the three strings for all possible rotations of string a.

Constraints

1n100000

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

The minimum difference is obtained when the first string is rotated cyclically once while the difference is maximum without any rotation.

Editor Image

?