ABC 009 C 辞書式順序ふたたび
続き。
実質リベンジみたいな。何を言っているのかは、わかる。実装はできないみたいな。まぁ、技術力不足なだけなんですけど()
以下、コードの説明。
i := T の 添字 j := i + 1 番目以降で、最も辞書的に小さい文字を探すための添字
あらかじめ、ans に、元々の文字列 S をリスト化してコピーしておく(あとあとswapしたいので、list 化)。
元々の S の i 番目よりも、辞書的に小さい文字を探して、本当に違う数が k 文字以下になるかどうか試すために、ss を用意する。 k 以下であれば、実際に、ansをスワップ。 これを繰り返すことで、違う数が k 文字以下であり尚且つ、辞書的に小さい文字列を得ることができる。
うーん、難しいなぁ。
from collections import Counter
n, k = map(int, input().split())
s = input()
ans = list(s)
for i in range(n):
l = i
for j in range(i+1, n):
# 現在の i 番目の文字より小さい文字があるか探す
if ans[l] > ans[j]:
# あった
ss = ans.copy()
ss[i], ss[j] = ss[j], ss[i]
# ss と比較したとき、違う数
diff = 0
for t in range(n):
if ss[t] != s[t]:
diff += 1
if diff <= k:
l = j
ans[i], ans[l] = ans[l], ans[i]
print("".join(ans))
