[Python] ABC009 C

問題

C – 辞書式順序ふたたび

ヒントと解説 (p.32-) が分かりやすいです。

「同じ長さの文字列s, t が与えられたとき、t を並び替えて、s との不一致の数を最小とする」ことを考えるには、結局、「それぞれの文字の数の差」を考えるだけで良い。

Abc009 from AtCoder Inc.

回答

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

S_sorted = sorted(S)

ans = ''
# ここまでの不一致文字数
count = 0

for i in range(N):
    # for c in (まだ使える文字を小さい順に)
    for c in S_sorted:
        # tmp := 仮の不一致文字数
        tmp = 0
        if c != S[i]:
            tmp = 1
        else:
            tmp = 0

        t = S_sorted[:]
        t.remove(c)
        for j in range(i+1, N):
            if S[j] in t:
                t.remove(S[j])
            else:
                tmp += 1

        # if (T + c にして大丈夫なら)
        if count + tmp <= K:
            ans += c
            S_sorted.remove(c)
            if c != S[i]:
                count += 1
            break
            
print(ans)