33716번 - 비장의 일격 (Large)

문제

본 문제와 비장의 일격 (Small) 문제는 입력 제한만 다른 동일한 문제이다.

영도는 어느 문자열에서 서로 다른 위치에 있는 같은 두 문자에 대해 비장의 일격을 최대 $K$번 날릴 수 있다. 비장의 일격을 맞으면 두 문자들과 두 문자 사이에 있는 문자열은 사라지며, 남은 문자열은 합쳐지게 된다. 단, 뾰족한 문자 X에는 비장의 일격을 날릴 수 없다. 길이가 $N$인, 알파벳 대문자로만 이루어진 문자열 $S$가 주어질 때 남아있을 수 있는 문자열의 최소 길이를 구하시오. 만약 문자열이 남아있지 않을 경우 0ドル$을 출력한다.

입력

첫 번째 줄에 문자열의 길이 $N$과 영도가 비장의 일격을 날릴 수 있는 횟수 $K$가 주어진다.

두 번째 줄에 문자열의 $S$가 주어진다.

출력

첫 번째 줄에 남아있을 수 있는 문자열의 최소 길이를 출력한다.

제한

• 1ドル \le N \le 1,000円,000円$
• 1ドル \le K \le 1,000円,000円$
• 입력으로 주어지는 모든 수는 정수이다.
• 입력으로 주어지는 문자열 $S$는 알파벳 대문자로만 이루어져 있다.

힌트