Atcoder(辞書順比較問題)について

前提

ABC009 C問題
にて、テストケースは通るのですが、どうしてもAC出来ません。
どこが違うのかご教授いただけると幸いです。

方針

辞書順比較なので、前方からソートされた文字列で埋めていけばいい。
ソートされた文字列が格納されているリストをsorted_Sとし、Sと、sorted_Sを前方から確認していく。

• Sとsorted_Sのi番目が一致すればcontinue
• 不一致なら、sorted_S[i]とS[i]を入れ替える

この操作が終わった後、cntで今現在のSと、もともとのS(noChange)を比較し、j番目の文字列が異なればcntに１プラス。cntがKを超えれば上記操作を行う前に定義したbefore_Sを表示し、終了。

python

import copy N, K = map(int, input().split())S = list(input())noChange = copy.deepcopy(S) sorted_S = sorted(S) for i in range(len(S)): if S[i] == sorted_S[i]: continue #操作する前のS before_S = copy.deepcopy(S) tmp = S[i] #辞書順比較したときに後ろに追いやる文字のインデックスを取得 idx = S[i:].index(sorted_S[i]) + i S[i] = sorted_S[i] S[idx] = tmp #もともとの文字列との差分を計算し、Kを超えていればbefore_Sを表示し終了 cnt = 0 for j in range(N): if noChange[j] != S[j]: cnt += 1 if cnt > K: print("".join(before_S)) exit() print("".join(S))