시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 1050 | 413 | 327 | 42.358% |
당신은 문자열 $S$를 선물 받았다. 하지만 당신은 오직 문자열 $T$만을 아름답다고 생각하기 때문에 기쁘지 않다. 당신은 같은 종류의 문자가 두 번 이상 나오는 것을 질색하기 때문에, $T$ 역시 모든 문자가 서로 다르다.
그러던 당신에게 좋은 생각이 떠올랐다. 바로 $S$의 문자들을 골라내서 $T$를 만드는 것이다! 당신은 $S$에서 문자들을 골라내서 $S$에서의 순서대로 이어 붙여 새 문자열을 만드는 시행을 여러 번 반복할 수 있다. 이때 $S$의 각 문자는 최대 한 번씩 골라낼 수 있다. 예를 들어, $S$가 "aabb"
이면 첫 번째 문자 "a"
와 세 번째 문자 "b"
를 골라 문자열 "ab"
를 만들고, 다시 두 번째 문자 "a"
와 네 번째 문자 "b"
를 골라 문자열 "ab"
를 만들 수 있다.
당신은 $T$를 가능한 한 많이 만들고 싶다. 만들 수 있는 $T$의 최대 개수를 구하는 프로그램을 작성해보자.
첫째 줄과 둘째 줄에 영어 소문자로만 이루어진 문자열 $S$와 $T$가 각각 주어진다. $(1\leq \left|S \right|\leq 1\,000\,000;$ $1\leq \left|T \right|\leq 26;$ $\left|T \right|\leq \left|S \right|)$
$T$의 모든 문자는 서로 다르다.
첫째 줄에 만들 수 있는 $T$의 최대 개수를 출력한다.
aabb ab
2
aabb ba
0
abba ab
1