You are given a string S of length N, containing lowercase Latin letters. You are also given an integer K.

You would like to create a new string S' by following the following process:
First, partition S into exactly K non-empty [subsequences] S_{1}, S_{2}, \ldots, S_{K}. Note that every character of S must be present in exactly one of the S_{i}.
Then, create S' as the concatenation of these subsequences, i.e, S' = S_{1} + S_{2} + \ldots + S_{K}, where + denotes string concatenation.

Determine the lexicographically smallest S' that can be created.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers, N and K.
- The second line of each test case contains the string S.

------ Output Format ------ 

For each test case, output on a new line the lexicographically smallest string S' that can be created.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
$S$ contains only lowercase Latin letters.
- Sum of $N$ over all cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
6 1
whizzy
14 2
aaacdecdebacde
4 3
dbca

----- Sample Output 1 ------ 
whizzy
aaaaccdecdebde
abcd
----- explanation 1 ------ 
Test Case $1$: $K = 1$, so our only option is to set $S' = S_{1} = whizzy$.

Test Case $2$: Partition $S = \textcolor{red}{aaa}\textcolor{blue}{cdecdeb}\textcolor{red}{ac}\textcolor{blue}{de}$ into $S_{1} = \textcolor{red}{aaaac}$ and $S_{2} = \textcolor{blue}{cdecdebde}$, to form $S' = aaaaccdecdebde$.

Test Case $3$: Partition $S = d\textcolor{blue}{bc}\textcolor{red}{a}$ into $S_{1} = \textcolor{red}{a}$, $S_{2} = \textcolor{blue}{bc}$, and $S_{3} = d$ to form $S' = abcd$.

In both test cases $2$ and $3$, it can be shown that no other partition gives a lexicographically smaller $S'$.

Source: codechef | Difficulty: VERY_HARD
Tags: String algorithms

Combinatorics

Data structures

Greedy algorithms


Solutions:
from itertools import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, k) = ma()
	s = st()
	z = set(list(s))
	if len(z) <= k:
		print(''.join(sorted(list(s))))
		continue
	if k == 1:
		print(s)
		continue
	freq = [0] * 26
	for i in s:
		freq[ord(i) - 97] += 1
	ind = {chr(i + 97): [] for i in range(26)}
	for i in range(n):
		ind[s[i]].append(i)
	res = ''
	vis = [0] * n
	flag = 0
	total = 0
	for i in range(k - 1):
		j = -1
		valid = 0
		if total == n:
			break
		while j < n:
			while valid < 26 and freq[valid] == 0:
				valid += 1
			if valid >= 26:
				break
			cur = chr(97 + valid)
			if ind[cur][-1] < j:
				break
			ex = ind[cur][-1]
			while ind[cur] and ind[cur][-1] > j:
				total += 1
				x = ind[cur].pop()
				vis[x] = 1
				res += cur
				freq[valid] -= 1
			j = ex
	left = ''
	for i in range(1 + j):
		if vis[i]:
			continue
		left += s[i]
	right = ''
	for i in range(j + 1, n):
		if vis[i]:
			continue
		right += s[i]
	cur_pos = 0
	rpart = [[] for i in range(26)]
	for i in range(len(right)):
		z = ord(right[i]) - 97
		rpart[z].append(i)
	for i in range(26):
		rpart[i] = rpart[i][::-1]
	prev = -1
	if left == '' and right == '':
		print(res)
		continue
	while 1:
		minchar = 999
		cmpord = ord(left[cur_pos]) - 97
		for i in range(26):
			if len(rpart[i]):
				if i <= cmpord:
					minchar = i
					break
		if minchar == 999:
			res += left
			res += right[prev + 1:]
			break
		elif minchar != cmpord:
			last = rpart[minchar][0]
			ok_char = chr(minchar + 97)
			res += ok_char * len(rpart[minchar])
			for i in range(prev + 1, last + 1):
				if right[i] != ok_char:
					left += right[i]
			for i in range(26):
				while rpart[i] and rpart[i][-1] <= last:
					rpart[i].pop()
			prev = last
		else:
			string1 = res + left + right[prev + 1:]
			ok_char = chr(minchar + 97)
			last = rpart[minchar][0]
			for i in range(prev + 1, last + 1):
				if right[i] != ok_char:
					left += right[i]
			ok_char = chr(minchar + 97) * len(rpart[minchar])
			string2 = res + ok_char + left + right[last + 1:]
			res = min(string1, string2)
			break
	print(res)


from sys import stdin, stdout
input = stdin.readline

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def back(n, s, k, ind, arr, mini):
	if ind == n:
		temp = ''
		for i in range(k):
			for j in range(n):
				if arr[j] == i:
					temp += s[j]
		mini[0] = min(mini[0], temp)
		return
	for i in range(k):
		arr[ind] = i
		back(n, s, k, ind + 1, arr, mini)

def f(n, k, s):
	arr = [0 for i in range(n)]
	mini = ['z' * n]
	back(n, s, k, 0, arr, mini)
	return ''.join(mini[0])
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().strip()
	arr = []
	for i in range(n):
		arr.append((s[i], i))
	arr = sorted(arr)
	all = SortedList(arr)
	ans = []
	p = k - 1
	while len(all):
		if not p:
			break
		p -= 1
		ind = all.pop(0)[1]
		last = ind
		ans.append((s[ind], ind))
		k = 0
		while k < len(all):
			(i, ind) = all[k]
			if i != all[0][0]:
				break
			if ind > last:
				ans.append((s[ind], ind))
				all.pop(k)
				last = ind
			else:
				k += 1
		if len(all) == 0:
			break
		if not p:
			first = float('inf')
			for (i, j) in all:
				first = min(first, j)
			pre = []
			mini = s[first]
			indi = -1
			for i in range(n - 1, last, -1):
				if s[i] <= mini and (s[i], i) in all:
					mini = s[i]
					indi = i
					pre.append((s[i], i))
					all.remove((s[i], i))
			ans += pre[::-1]
	arr = list(all)
	arr.sort(key=lambda x: x[1])
	l = len(ans)
	ind = -1
	arr2 = arr.copy()
	for i in range(l - 1, -1, -1):
		if not len(arr):
			break
		if ans[i][0] == arr[0][0]:
			arr2.append(ans[i])
			ind = i
		else:
			break
	arr2.sort(key=lambda x: x[1])
	if ind == -1:
		ans += arr
		ans = [i[0] for i in ans]
	else:
		temp1 = [i[0] for i in ans[:ind] + arr2]
		temp2 = [i[0] for i in ans + arr]
		ans = min(temp1, temp2)
	print(''.join(ans))