아나그램 회피

시간 제한1초메모리 제한64 MB

요약

문자열 s가 주어질 때, 고른 것들 중 서로 애너그램 관계인 두 문자열이 없도록 선택할 수 있는 부분수열의 최대 개수를 구한다.

문제

두 문자열이 아나그램이라는 것은 첫 번째 문자열의 글자를 재배열해 두 번째 문자열로 만들 수 있다는 뜻이다. 예를 들어 "listen"과 "silent"는 아나그램이지만, "master"와 "nearest"는 아니다.

문자열 $s = s_1 s_2 \dots s_n$ 의 부분수열은 $1 \le a_1 < a_2 < \dots < a_k \le n$ 인 문자열 $s_{a_1} s_{a_2} \dots s_{a_k}$ 이다.

문자열 $s$ 가 주어질 때, 결과 목록에 있는 어떤 두 문자열도 아나그램이 되지 않도록 부분수열을 나열할 수 있는 최대 개수를 구하라.

영소문자로 이루어진 길이 $60$ 이하의 문자열 $s$ 가 한 줄에 주어진다.

답을 한 수로 출력한다.

첫 번째 예시에서 결과 목록은 "j", "o", "jj", "jo", "oo", "jjo", "joo", "jojo"가 될 수 있다.