Read problems statements in Mandarin Chinese , Russian and Vietnamese as well. 
Akhil comes across a string S of length N. He started wondering about the smallest lexicographical subsequence of string S of length K.
A subsequence of a string is formed by deleting some characters (possibly none) from it's original string.
A string A is said to be lexicographically smaller than the string B of the same length if at the first position where A and B differ, A contains a letter which appears earlier in the dictionary than the corresponding letter in B.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows:
First line of each test case will contain string S
Second line of each test case will contain an integer K.

------ Output ------ 

For each test case, output a single line containing the lexicographically smallest subsequence of S of length K.

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

$1 ≤ T ≤ 5$
$1 ≤ K ≤ N$
$S consists of lowercase English alphabet characters, i.e. from 'a' to 'z'.$

------ Subtasks ------ 

Subtask #1 (10 points) : 1 ≤ |S| ≤ 100
Subtask #2 (20 points) : 1 ≤ |S| ≤ 10^{3}
Subtask #3 (70 points) : 1 ≤ |S| ≤ 10^{5}

----- Sample Input 1 ------ 
2
abdc
3
bacb
2
----- Sample Output 1 ------ 
abc
ab
----- explanation 1 ------ 
Example case 1. "abc" is the smallest lexicographical subsequence out of ["abd", "bdc", "abc", "adc"].
Example case 2. "ab" is the smallest lexicographical subsequence of length 2.

Source: codechef | Difficulty: HARD
Tags: String algorithms

Combinatorics

Data structures


Solutions:
def segmentTree(arr, segTree, low, high, pos):
	if low == high:
		segTree[pos] = (arr[low], low)
		return
	mid = (low + high) // 2
	segmentTree(arr, segTree, low, mid, 2 * pos + 1)
	segmentTree(arr, segTree, mid + 1, high, 2 * pos + 2)
	aa = segTree[2 * pos + 1]
	bb = segTree[2 * pos + 2]
	if aa[0] != bb[0]:
		segTree[pos] = aa if aa[0] < bb[0] else bb
	else:
		segTree[pos] = aa if aa[1] < bb[1] else bb

def qr(segTree, qLow, qHigh, low, high, pos):
	if qLow <= low and qHigh >= high:
		return segTree[pos]
	if qLow > high or qHigh < low:
		return ('zzz', 1000)
	mid = (low + high) // 2
	b = qr(segTree, qLow, qHigh, low, mid, 2 * pos + 1)
	c = qr(segTree, qLow, qHigh, mid + 1, high, 2 * pos + 2)
	if b[0] != c[0]:
		a = b if b[0] < c[0] else c
	else:
		a = b if b[1] < c[1] else c
	return a
for t in range(int(input())):
	arr = list(input())
	ans = ''
	n = int(input())
	nn = 1
	while nn < len(arr):
		nn *= 2
	nn = nn * 2 - 1
	arrTree = [0 for x in range(nn)]
	segmentTree(arr, arrTree, 0, len(arr) - 1, 0)
	start = 0
	while n > 0:
		end = len(arr) - n
		xx = qr(arrTree, start, end, 0, len(arr) - 1, 0)
		start = int(xx[1]) + 1
		ans += xx[0]
		n = n - 1
	print(ans)


from heapq import heapify, heappush, heappop
st = 'abcdefghijklmnopqrstuvwxyz'
d = {}
d1 = {}
for i in range(26):
	d[st[i]] = i
	d1[i] = st[i]
for _ in range(int(input())):
	s = input()
	k = int(input())
	heap = []
	heapify(heap)
	n = len(s)
	for i in range(n - k + 1):
		ind = d[s[i]]
		heappush(heap, [ind, i])
	a = heappop(heap)
	fin = d1[a[0]]
	ind = a[1]
	for j in range(n - k + 1, n, 1):
		heappush(heap, [d[s[j]], j])
		while heap and heap[0][1] < ind:
			a = heappop(heap)
		a = heappop(heap)
		fin += d1[a[0]]
		ind = a[1]
	print(fin)


def smallestSubsequence(s, k):
	toRem = len(s) - k
	ind = 0
	while ind < len(s) - 1 and toRem > 0:
		if s[ind] > s[ind + 1]:
			s = s[:ind] + s[ind + 1:]
			toRem -= 1
			ind -= 1
			if ind < 0:
				ind = 0
		else:
			ind += 1
	s = s[:k]
	return s
for ii in range(int(input())):
	s = input()
	k = int(input())
	print(smallestSubsequence(s, k))


t = int(input())

def spush(a, elem):
	a.append(elem)

def spop(a, size):
	j = a.pop(size - 1)
	return j
for i in range(t):
	s = input()
	k = int(input())
	a = []
	size = 1
	a.append(s[0])
	p = len(s)
	zz = 1
	while zz < p:
		ss = s[zz]
		chm = a[size - 1]
		while ss < chm and size + (p - zz - 1) >= k:
			spop(a, size)
			size -= 1
			if size == 0:
				break
			chm = a[size - 1]
		if size < k:
			size += 1
			spush(a, ss)
		zz += 1
	o = ''
	for t in range(k):
		o = o + a[t]
	print(o)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	k = int(input())
	c = 0
	ans = []
	for j in range(k):
		ans.append('')
	for i in range(n):
		if i == 0:
			ans[i] = s[i]
			c += 1
		else:
			while s[i] < ans[c - 1] and c + (n - i) > k:
				ans[c - 1] = ''
				c -= 1
			if c < k:
				ans[c] = s[i]
				c += 1
	anss = ''
	for a in ans:
		anss += a
	print(anss)


import sys
sys.setrecursionlimit(100000)

def sub(s, k):
	if k == 0:
		return ''
	if len(s) == k:
		return s
	if len(s) == 0:
		return ''
	d1 = 1
	if len(s) - 1 >= k:
		s1 = sub(s[:-1], k)
	else:
		d1 = 0
	s2 = sub(s[:-1], k - 1)
	if d1 == 0:
		return s2 + s[-1]
	if s1 < s2 + s[-1]:
		return s1
	return s2 + s[-1]

def solve(s, k):
	stack = []
	left = 0
	l = len(s)
	for x in range(l):
		if left == 0:
			stack.append(s[x])
			left += 1
		else:
			while left > 0 and stack[-1] > s[x] and (l - x + left - 1 >= k):
				stack.pop()
				left -= 1
			stack.append(s[x])
			left += 1
	return ''.join(stack[:k])
T = int(input())
for t in range(T):
	S = input()
	K = int(input())
	print(solve(S, K))