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

Question

前提

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を表示し、終了。

追記

以下のコードの"以下修正"部分を解答頂いたように修正しましたが、正解数は増えたものの、完全に正解することはできませんでした。

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 = "".join(S).rfind(sorted_S[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))

Answer 1

例えばN=4,K=2,S=bcaaである時、本来の答えは一番前と後ろを入れ替えたacabですが、上のプログラムですとacbaになってしまいます。
index(s)は最前にある文字sを取得するので、最後方のものと入れ替えるような工夫をすればACできると思います。