C++ Solution using Stack and Sort


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

int n = A.size();
// Step1: Find a swap which will make the number larger - a digit from right side
// should be swapped with a smaller number on the left side: 218765 -> 5 swapped with 1

// Step2: sort all the digits on the right of 5 to get the minimum - Remember that we 
// need to find a number which greater than the given no. AND smallest in the set of numbers
//greater than the given number.

stack<int> st;
st.push(n-1);

int i = n-1;

while(!st.empty()  &&  --i >= 0){
    if(A[st.top()] > A[i]){
        int r;
        while(!st.empty() && A[st.top()] > A[i]){
            r = st.top();
            st.pop();
        }
        swap(A[i], A[r]);
        sort(A.begin()+i+1, A.end());
        return A;
    }
    st.push(i);
}
return "-1";
}