問題
C – 辞書式順序ふたたび
ヒントと解説 (p.32-) が分かりやすいです。
「同じ長さの文字列s, t が与えられたとき、t を並び替えて、s との不一致の数を最小とする」ことを考えるには、結局、「それぞれの文字の数の差」を考えるだけで良い。
回答
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)