Letter Wheels

Interview

Time limit3sMemory limit512 MB

Summary

Three cyclic strings over {A,B,C}; rotate each independently to make every column have three distinct letters, minimizing total rotation steps.

Level: Medium7 of 10
Topics: String, Brute force, Math, Implementation
Solved: No attempts yet

Problem

Three horizontal wheels of letters are stacked one on top of the other, all with the same number of columns. Each wheel has one letter, either ‘A’, ‘B’ or ‘C’, in each of its columns on the edge of the wheel. You may rotate the wheels to adjust the positions of the letters. In a single rotation, you can rotate any single wheel to the right or to the left by one column. The wheels are round, so the first column and last column are adjacent.

You would like to determine whether it is possible to rotate the wheels so that every column has three distinct letters across the three wheels, and if so, determine the minimum number of rotations required.

Input

The input has exactly three lines. Each line has a string $s$ ( $2 \le |s| \le 5 \cdot 10^3$ ) consisting only of upper-case letters ‘A’, ‘B’ or ‘C’, describing the letters of one wheel in their initial positions. All three strings will be of the same length.

Output

Output a single integer, which is the minimum number of rotations required, or −1 if it isn’t possible.

Examples3

Example 1
Input
```
ABC
ABC
ABC
```
Expected output
```
2
```
Example 2
Input
```
ABBBAAAA
BBBCCCBB
CCCCAAAC
```
Expected output
```
3
```
Example 3
Input
```
AABB
BBCC
ACAC
```
Expected output
```
-1
```