Implementation of prev_permutation

In my previous posts, I discussed about various approaches to find the next number in order. The main idea for that is the function of next_permutation in C++, or equivalent implementations in C or Java. Now, I am trying to implement the opposite function prev_permutation.

The function takes a string as input, update the string to the previous one in lexicographical order if there is, and return a bool value. If there is a smaller string, return true; if not, return false and update the string from the smallest to the greatest.

Idea:

1. Search back from the end, find the first greater character compared to the one immediately after it.
2. Search back from the end again, find the first smaller one compared to the great character just found.
3. Swap the 2 characters found from above 2 steps.
4. Reverse the rest string after the character location found in Step 1.