만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

문자열 자르기

시간 제한10초메모리 제한512 MB

요약
문자열 s와 정수 k가 주어질 때, 겹치지 않는 부분 문자열을 최대 k개 지워 사전순으로 가장 큰 문자열을 만듭니다.
난이도

어려움10점 중 8점

유형
문자열, 그리디, 문자열 매칭
정답자
아직 제출이 없습니다

문제

문자열 ss와 정수 kk가 주어진다. ss에서 서로 겹치지 않는 부분 문자열을 최대 kk개까지 제거할 수 있다. 남은 문자열 중 사전 순으로 가장 큰 문자열을 구하라.

예를 들어 문자열 abcdcada와 k=2k=2가 주어졌을 때, [abc]d[ca]da 부분을 골라 제거하면 dda를 얻을 수 있다.

입력

첫 줄에 테스트 케이스의 개수 cc (1≤c≤2×1051 \le c \le 2 \times 10^5)가 주어진다. 이후 cc개의 줄에는 정수 kk와 문자열 ss가 공백으로 구분되어 한 줄에 하나씩 주어진다 (1≤k≤∣s∣≤1051 \le k \le |s| \le 10^5, s∈[a−z]∗s \in [a-z]^*). 입력에 주어지는 모든 문자열 길이의 합은 10610^6 이하이다.

출력

각 테스트 케이스마다, ss에서 서로 겹치지 않는 부분 문자열을 kk개 이하로 제거하여 만들 수 있는 문자열 중 사전 순으로 가장 큰 문자열을 출력한다.

예제1

  1. 예제 1

    입력
    4
2 abcdcada
1 ababb
2 ababb
1 dadbdcdbdad
    예상 출력
    dda
bb
bbb
ddcdbdad