Not a Cheap String (Codeforces 1702D)
Tags: Greedy, greedy

Let $$$s$$$ be a string of lowercase Latin letters. Its price is the sum of the indices of letters (an integer between 1 and 26) that are included in it. For example, the price of the string abca is $$$1+2+3+1=7$$$.The string $$$w$$$ and the integer $$$p$$$ are given. Remove the minimal number of letters from $$$w$$$ so that its price becomes less than or equal to $$$p$$$ and print the resulting string. Note that the resulting string may be empty. You can delete arbitrary letters, they do not have to go in a row. If the price of a given string $$$w$$$ is less than or equal to $$$p$$$, then nothing needs to be deleted and $$$w$$$ must be output.Note that when you delete a letter from $$$w$$$, the order of the remaining letters is preserved. For example, if you delete the letter e from the string test, you get tst.

Input: The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test. The following are descriptions of $$$t$$$ test cases.Each case consists of two lines.The first of them is the string $$$w$$$, it is non-empty and consists of lowercase Latin letters. Its length does not exceed $$$2\cdot10^5$$$.The second line contains an integer $$$p$$$ ($$$1 \le p \le 5\,200\,000$$$).It is guaranteed that the sum of string lengths $$$w$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: Output exactly $$$t$$$ rows, the $$$i$$$-th of them should contain the answer to the $$$i$$$-th set of input data. Print the longest string that is obtained from $$$w$$$ by deleting letters such that its price is less or equal to $$$p$$$. If there are several answers, then output any of them.Note that the empty string  — is one of the possible answers. In this case, just output an empty string.


Sample Inputs:
5
abca
2
abca
6
codeforces
1
codeforces
10
codeforces
100

Sample Outputs:
aa
abc

cdc
codeforces

Solution (Python):
x = int(input())
odg = []
for i in range(0, x):
    l = input()
    w = int(input())
    ls = sorted(l)
    price = 0
    granica = None
    for j in range(0, len(ls)):
        price += ord(ls[j]) - 96
        if price > w:
            granica = j
            break
    if granica != None:
        visak = ls[granica:]
    else:
        visak = []
    y = 0
    visak = ''.join(visak)
    while visak != '':
        l = l.replace(visak[0], '', visak.count(visak[0]))
        visak = visak.replace(visak[0], '')
    odg.append(l)
for e in odg:
    print(e)

Solution (Python):
d = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26}
for _ in range(int(input())):
    w = input()
    p = int(input())
    ans = {}
    k = list(w)
    k.sort()
    x = 0
    for i in k:
        x += d[i]
        if x <= p:
            if i not in ans:
                ans[i] = 1
            else:
                ans[i] += 1
        else:
            break
    s = ''
    for x in w:
        if x in ans and ans[x] > 0:
            s += x
            ans[x] -= 1
    print(s)

Solution (Python):
t = int(input())
for _ in range(t):
    word = input()
    p = int(input())
    y = [c for c in word]
    y.sort()
    g = [ord(h) - ord('a') + 1 for h in y]
    val = sum(g)
    if val <= p:
        print(word)
    else:
        l = 0
        k = len(g)
        mid = (l + k + 1) // 2
        while l < k:
            mid = (l + k + 1) // 2
            if sum(g[:mid]) == p:
                break
            elif sum(g[:mid]) > p:
                k = mid - 1
            else:
                l = mid
        dict = {}
        if l == k and sum(g[:l]) <= p:
            mid = l
        for i in range(mid):
            f = y[i]
            if f in dict:
                dict[f] += 1
            else:
                dict[f] = 1
        ans = ''
        for c in word:
            if c in dict:
                ans += c
                dict[c] -= 1
                if dict[c] == 0:
                    dict.pop(c)
        print(ans)