세 포장대의 균형 작업 구간

문제

물류 창고에는 A, B, C라는 이름의 포장대가 하나씩 있다. 작업 기록 장치는 상자 하나의 포장이 끝날 때마다 해당 포장대의 이름을 한 글자 기록한다. 따라서 하루의 기록은 A, B, C로만 이루어진 문자열이다. 문자열의 각 글자는 상자 하나에 대응하며, 기록 순서는 포장이 끝난 순서이다. 창고 관리자는 세 포장대가 같은 수의 상자를 처리한 연속 작업 구간을 찾아 교육 자료로 사용하려 한다. 연속 작업 구간은 기록에서 시작 위치 L과 끝 위치 R을 정하고, L번부터 R번까지의 모든 글자를 빠짐없이 포함한 부분이다. 위치 번호는 1번부터 시작하고 양 끝 위치를 모두 포함한다. 구간 중간의 기록을 빼거나 순서를 바꾸는 것은 허용하지 않는다. 교육 자료로 사용할 수 있으려면 해당 구간에 등장하는 A의 개수, B의 개수, C의 개수가 모두 같아야 한다. 구간은 비어 있을 수 없으므로, 사용할 수 있는 구간에는 각 포장대의 기록이 적어도 하나씩 들어간다. 전체 기록에서 세 글자의 개수가 같을 필요는 없으며, 선택한 구간 안에서만 같으면 된다. 관리자는 사용할 수 있는 구간 중 길이가 가장 긴 것을 고른다. 길이는 R-L+1이다. 가장 긴 구간이 여러 개이면 시작 위치 L이 가장 작은 구간을 고른다. 길이와 시작 위치가 정해지면 끝 위치도 하나로 정해지므로 추가 동점 규칙은 없다. 입력 기록에 특정 포장대의 이름이 한 번도 등장하지 않는 등 조건에 맞는 구간이 없을 수도 있다. 이런 경우에는 길이와 양 끝 위치를 모두 0으로 출력한다. 기록이 주어질 때 선택할 구간의 길이와 시작 위치, 끝 위치를 구하는 프로그램을 작성한다. 서로 다른 위치에 같은 글자가 나타나더라도 각 글자는 별도의 상자 기록으로 센다.

입력

첫째 줄에 기록 길이인 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 대문자 A, B, C 중 하나이다.

출력

선택한 구간의 길이, 시작 위치 L, 끝 위치 R을 공백으로 구분하여 한 줄에 출력한다. 길이가 최대인 구간이 여러 개이면 L이 가장 작은 구간을 출력한다. 조건을 만족하는 구간이 없으면 0 0 0을 출력한다.

8
AABCBCAB

6 1 6

5
AACAA

0 0 0

9
ABCABCABC

9 1 9

출처: Devin.KR 자체 제작