Similar Strings
Practice
3.7 (3 votes)
Algorithms
Convolution
Fast fourier transform
Medium
Problem
33% Success 883 Attempts 50 Points 3s Time Limit 256MB Memory 1024 KB Max Code

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 \(\sum\limits_{i=1}^n \ |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

\(1 \le n \le 100000\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
11 votes
Tags:
Divide-and-conquer algorithmFast Fourier transformGenerating FunctionsMedium
Points:50
2 votes
Tags:
AlgorithmsApprovedFFTFast Fourier transformMedium