레터 휠

면접 대비

시간 제한3초메모리 제한512 MB

요약

세 개의 순환 문자열이 주어질 때, 각 바퀴를 독립적으로 회전시켜 모든 열에서 세 글자가 서로 다르게 만들고, 필요한 최소 회전 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 문자열, 완전 탐색, 수학, 구현
정답자: 아직 제출이 없습니다

문제

글자가 적힌 가로 방향의 휠 세 개가 위아래로 쌓여 있고, 세 휠의 열 개수는 모두 같다. 각 휠은 가장자리의 모든 열에 ‘A’, ‘B’, ‘C’ 중 하나의 글자가 적혀 있다. 휠을 회전시켜 글자의 위치를 조정할 수 있다. 한 번의 회전으로 휠 하나를 왼쪽 또는 오른쪽으로 한 열만큼 돌릴 수 있다. 휠은 둥글기 때문에 첫 번째 열과 마지막 열은 서로 인접해 있다.

세 휠을 회전시켜 모든 열에서 세 휠의 글자가 서로 다르게 만들 수 있는지 판별하고, 가능하다면 필요한 최소 회전 횟수를 구하시오.

입력

입력은 정확히 세 줄이다. 각 줄에는 대문자 ‘A’, ‘B’, ‘C’로만 이루어진 문자열 $s$ ( $2 \le |s| \le 5 \cdot 10^3$ )가 주어지며, 이는 한 휠의 초기 글자 배치를 나타낸다. 세 문자열의 길이는 모두 같다.

출력

필요한 최소 회전 횟수를 정수로 출력한다. 불가능하면 −1을 출력한다.

예제3

예제 1
입력
```
ABC
ABC
ABC
```
예상 출력
```
2
```
예제 2
입력
```
ABBBAAAA
BBBCCCBB
CCCCAAAC
```
예상 출력
```
3
```
예제 3
입력
```
AABB
BBCC
ACAC
```
예상 출력
```
-1
```