Submission #2179814

---

Source Code Expand

def get_diff(S, T):
    count = 0
    for i, j in zip(S, T):
        if i != j:
            count += 1
    return count


def can_sort_with_error(S, T, K):
    sorted_S = sorted(S)
    sorted_T = sorted(T)
    for i in sorted_S:
        if i in sorted_T:
            sorted_T.remove(i)
    return len(sorted_T) <= K

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

sorted_S = sorted(S)
T = ''

not_used_strings = sorted_S[:]

for i, (s, sorted_s) in enumerate(zip(S, sorted_S)):
    if s == sorted_s:
        T += s
        not_used_strings.remove(s)
        continue
    else:
        for j, candidate in enumerate(not_used_strings):
            if can_sort_with_error(
                S[i + 1:],
                not_used_strings[:j] + not_used_strings[j + 1:],
                K - get_diff(S[:i + 1], T + candidate)
                ):
                T += candidate
                not_used_strings.remove(candidate)
                break
        else:
            T += S[i + 1:]
            break

print(T)

Submission Info

Judge Result