Submission #1607170

---

Source Code Expand

def solve(N, K, S):
    S = [x for x in S]
    T1 = []
    T2 = S.copy()
    dictS = {chr(ord('a')+i): S.count(chr(ord('a')+i)) for i in range(26)}
    dictT = dictS.copy()
    atoz = [chr(ord('a')+i) for i in range(26)]
    
    for i in range(N):
        if K == 0:
            break
        T2.sort()
        flag = False
        if T2[0] == S[i]:
            pos = 0
            flag = True
        else:
            for j in range(len(T2)):
                c = T2[j]
                dictT[c] -= 1
                dictS[S[i]] -= 1
                cnt = 0
                for x in atoz:
                    cnt += min(dictS[x], dictT[x])
                cnt = N - 1 - i - cnt
                dictT[c] += 1
                dictS[S[i]] += 1
                if K-1-cnt >= 0:
                    pos = j
                    K -= 1
                    flag = True
                    break
        if flag == False:
            break

        c = T2[pos]
        dictS[S[i]] -= 1
        dictT[c] -= 1
        T1.append(c)
        T2.pop(pos)

    s = len(T1)
    T3 = ['.'] * len(T2)
    for i in range(s, N):
        if dictT[S[i]] > 0:
            T3[i-s] = S[i]
            dictT[S[i]] -= 1
    for i in range(s, N):
        if T3[i-s] != '.':
            continue
        for x in atoz:
            if dictT[x] > 0:
                T3[i-s] = x
                dictT[x] -= 1
    print(''.join(T1+T3))

N, K = list(map(int, input().split()))
S = input()
solve(N, K, S)

Submission Info

Judge Result