ABBC timer 3초 memory 1024MB

A, B, C로만 이루어졌고 길이가 |S|인 문자열 S가 있다. 당신은 이 문자열에 다음과 같은 시행을 할 수 있다.

• A와 그 뒤에 있는 B를 지운다.

• B와 그 뒤에 있는 C를 지운다.

• 각 문자는 최대 한 번만 지울 수 있다.

예를 들어 ABCBA를 보자. 각 문자에 왼쪽부터 1번, 2번, 3번. . . 과 같이 번호를 붙이면 다음과 같이 시행할 수 있다.

• 1번 A와 2번 B를 지운다. 이 경우 시행의 횟수는 1번이고, 남은 문자열은 CBA이다.   어떤 두 문자를 골라도 시행의 조건을 만족시킬 수 없으므로, 더 이상 시행을 할 수 없다.

• 1번 A와 4번 B를 지우고, 이어 2번 B와 3번 C를 지운다.   이 경우 시행의 횟수는 2번이고 남은 문자열은 A이다.   문자열에 남은 문자가 하나이므로, 더 이상 시행을 할 수 없다.

이외에도 시행을 할 수 있는 여러 경우의 수가 있다.

시행을 할 수 있는 최대 횟수를 구해라.​

제약 조건

• 1 ≤ |S| ≤ 300,000

• S의 모든 문자는 A, B, C 중 하나이다.

부분문제

1. (5점) S의 모든 문자는 A, B 중 하나이다.

2. (20점) |S| ≤ 300.

3. (32점) |S| ≤ 1,000.

4. (43점) 추가 제약 조건 없음.​