Submission #4076340

---

Source Code Expand

#include <stdio.h>
#include <iostream>
#include <string>
#include <sstream>
#include <iterator>
#include <algorithm>

using namespace std;

int countDiff(string a, string b){
    int cnt = 0;
    for(unsigned int i = 0; i < a.length(); i++){
        if(a[i] != b[i]){
            cnt++;
        }
    }
    return cnt;
}
int findIndexFromBack(string str, char c){
    int i = str.length() - 1; 
    for(;i >= 0; i--){
        if(str[i] == c){
            break;
        }
    }
    if(i < 0){
        return -1;
    }
    return i;
}
string exchangeChar(string str, int a, int b){
    char buf = str[a];
    str[a] = str[b];
    str[b] = buf;
    return str;
}
string makeSmallest(int n, int k, string inp){
    string copied, original;
    copied = original = inp;
    sort(copied.begin(), copied.end());
    int ind, i;
    i = 0;
    string res = "";
    for(; i < n; i++){
        if(inp[i] == copied[i]){
            res += copied[i];
            continue;
        }
        ind = findIndexFromBack(inp, copied[i]);
        if(ind < 0){
            throw logic_error("index cant beb null");
        }
        inp = exchangeChar(inp, i, ind);
        res += inp[i];
        k--;
        if(k <= countDiff(original.substr(i+1, n), inp.substr(i+1, n))){
            i++;
            break;
        }
    }
    res += inp.substr(i, n);
    return res;
}

int main (void){
    int n, k;
    string inp;
    cin >> n >> k >> inp;
    cout << makeSmallest(n,k,inp) << endl;
    return 0;
}

Submission Info

Judge Result