C++ solution using swap and sort


#1
string Solution::solve(string A) {

    multiset<char> ms;
    string res="";
    bool flag = false;
    int len = A.size(), pos1 = -1, pos2 = -1;

    // find any element which is smaller than any element on right
    for(int i=len-2; i>=0 && !flag; i--){

        int minVal = INT_MAX;
        pos1 = i;

        // find element to right least greater than vec[i]
        for(int j=len-1; j>i; j--){
            if(A[j] > A[i] && minVal > A[j]) {
                minVal = A[j];
                pos2 = j;
                flag = true;
            }
        }
    }
    if(!flag)  return "-1";

    // swap both and sort remaining in asc order
    swap(A[pos1], A[pos2]);

    for(int i=pos1+1; i<len; i++)
        ms.insert(A[i]);

    for(int i=0; i<=pos1; i++)
        res += (A[i]);

    for(auto it: ms)
        res += (it);

    return res;
}