Problem:
Swapping Characters You are given a string and a number k . You are suggested to generate new strings by swapping any adjacent pair of characters in the string up to k times. Write a program to report the lexicographically smallest string among them. Input The input is given in the following format.  s  k  The first line provides a string s . The second line provides the maximum number of swapping operations k (0 ≤ k ≤ 10 9 ). The string consists solely of lower-case alphabetical letters and has a length between 1 and 2 × 10 5 . Output Output the lexicographically smallest string. Sample Input 1 pckoshien
3 Sample Output 1 ckopshien Sample Input 2 pckoshien
10 Sample Output 2 cekophsin

Solution (Python):
import sys

def main():
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    s = SI()
    n = len(s)
    k = NI()

    def conv(x):
        return ord(x) - ord('a')

    bit = [0] * (n+1)

    def bit_add(i):
        while i <= n:
            bit[i] += 1
            i += i & (-i)

    def bit_sum(i):
        ret = 0
        while i > 0:
            ret += bit[i]
            i -= i & (-i)
        return ret

    z = [0] * n
    top = [-1] * 26
    nxt = [-1] * n
    bef = [-1] * 26
    for i in range(n):
        cv = conv(s[i])
        if bef[cv] >= 0:
            nxt[bef[cv]] = i
        bef[cv] = i
        if top[cv] < 0:
            top[cv] = i

    ans = []
    while k > 0:
        for i in range(26):
            if top[i] < 0: continue
            p = top[i]
            cost = p - bit_sum(p+1)
            if cost <= k:
                ans.append(chr(ord('a')+i))
                z[top[i]] = 1
                k -= cost
                top[i] = nxt[top[i]]
                bit_add(p+1)
                break
        else:
            break


    for i in range(n):
        if z[i] == 0: ans.append(s[i])
    print(*ans,sep='')


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left as bl

def main():
  s = list(map(ord, list(input())))
  k = int(input())
  used = []
  used_index = []
  pos_dict = {}
  as_a = ord("a")
  as_z = ord("z")
  for i, v in enumerate(s):
    if v in pos_dict:
      pos_dict[v].append(i)
    else:
      pos_dict[v] = [i]
  keys = sorted(pos_dict.keys())
  for key in keys:
    pos_dict[key].reverse()
  
  while k:
    for key in keys:
      init = pos_dict[key][-1]
      pre_used = bl(used_index, init)
      cost = init - pre_used
      if cost <= k:
        k -= cost
        used.append(key)
        ins = bl(used_index, init)
        used_index.insert(ins, init)
        pos_dict[key].pop()
        if not pos_dict[key]:
          keys.remove(key)
        break
    else:
      break
  
  used_index.sort(reverse=True)
  for i in used_index:
    s.pop(i)
  print("".join(map(chr, used + s)))

main()