문제 태그

• 누적합
• 포함 배제 원리
• 해시

한국어 문제 해석

문자열 S가 A, B, C 세 문자로만 이루어진다.

부분 문자열 안에서 A의 개수, B의 개수, C의 개수가 모두 서로 다른 경우만 세고 싶다.

이 조건을 만족하는 모든 부분 문자열의 개수를 구한다.

문제 요약

• 부분 문자열마다 세 문자의 등장 횟수를 본다.
• 세 개의 등장 횟수가 전부 달라야 한다.
• 직접 세기보다는, 두 개 이상 같아지는 경우를 전체에서 빼는 방식이 핵심이다.

예시 워크스루

문자열이 AABBCC라고 하자.

부분 문자열 AAB를 보면 A는 2번, B는 1번, C는 0번 나온다.

세 수가 2, 1, 0으로 모두 다르므로 정답에 포함된다.

같은 방식으로 ABB, BBC, BCC도 포함된다.

반면 ABC는 세 문자가 모두 1번씩 등장하므로 세 수가 같아져 탈락한다.

결국 이 예시에서 답은 4가 된다.