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 ≤ 109). The string consists solely of lower-case alphabetical letters and has a length between 1 and 2 &times; 105.

Output

  Output the lexicographically smallest string.

Sample Input 1

pckoshien
3

Sample Output 1

ckopshien

Sample Input 2

pckoshien
10

Sample Output 2

cekophsin



Sample input:
pckoshien
3


Sample output:
ckopshien

Submission status: Wrong Answer

Solution code:
def solve(k,s):
    for i in range(len(s)):
        ss = s[i:i+k+1]
        min_c = min(ss)
        min_i = s.index(min_c)

        if min_i != i:
            k -= (min_i-i)
            s.pop(min_i)
            s.insert(i,min_c)
        if k == 0:
            break
            
    return s

s = list(input())
k = int(input())

o = solve(k,s)
print("".join(o))

Submission status: Time Limit Exceeded

Solution code:
def solve(k,s):
    for i in range(len(s)):
        ss = s[i:i+k+1]
#        print("ss={}".format(ss))
        min_c = min(ss)
        min_i = ss.index(min_c)

        if min_i != 0:
            k -= min_i
            s.pop(i+min_i)
            s.insert(i,min_c)
        if k == 0:
            break
#        print("".join(s))
            
    return s

s = list(input())
k = int(input())

o = solve(k,s)
print("".join(o))

Submission status: Time Limit Exceeded

Solution code:
def mymin(s,f,l):
    mc = 'z'
    mi = 0

    for i in range(min([l,len(s)-f])):
        if s[f+i] < mc:
            mc = s[f+i]
            mi = i
    return (mc,mi)

def solve(k,s):
    min_i = 0
    min_c = 'z'
    nskip = 0
    total = 0
    
    for i in range(len(s)):
        (min_c,min_i) = mymin(s,i,k+1)
        total += 1
        if min_i != 0:
            k -= min_i
            s.pop(i+min_i)
            s.insert(i,min_c)
        else:
            nskip += 1
        if k == 0:
            break
#    print("total={} nskip= {}".format(total,nskip))
    return s

s = list(input())
k = int(input())

o = solve(k,s)
print("".join(o))

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
k = int(input())
j = 0
while True:
    i = s[j:j + k + 1].index(min(s[j:j + k + 1]))
    s = s[:j] + [s[j + i]] + s[j :j + i] + s[j + i + 1:]
    j += 1
    k -= i
    if k == 0 or j >= len(s) - 1:
        break
print("".join(s))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Runtime Error

Solution code:
def solve(k,s):
    if k == 0:
        return s
    elif s == []:
        return []
    else:
        ss = s[0:k+1]
        min_c = min(ss)
        min_i = ss.index(min_c)

        if min_i == 0:
            ss = s[1:len(s)]
            return [s[0]] + solve(k,ss)
        else:
            s.pop(min_i)
            k -= min_i
            return [min_c] + solve(k,s)

s = list(input())
k = int(input())

o = solve(k,s)
print("".join(o))

Submission status: Runtime Error

Solution code:
s = list(input())
k = int(input())
j = 0
while True:
    i = s[j:j + k + 1].index(min(s[j:j + k + 1]))
    s = s[:j] + [s[j + i]] + s[j :j + i] + s[j + i + 1:]
    j += 1
    k -= i
    if k == 0:
        break
print("".join(s))

Submission status: Runtime Error

Solution code:
s = list(input())
k = int(input())
j = 0
while True:
    i = s[j:j + k + 1].index(min(s[j:j + k + 1]))
    s = s[:j] + [s[j + i]] + s[j :j + i] + s[j + i + 1:]
    j += 1
    k -= i
    if k == 0 or j == len(s) - 1:
        break
print("".join(s))