Given a string s, find lexicographically previous permutation of it.
For example: Lexicographically previous permutation of “4321” is “4312". If the string is sorted in ascending order, then the lexicographically previous permutation doesn’t exist.
Example 1:
Input: s = "4321"
Output: "4312"
Explanation: lexicographically previous
permutation of “4321” is “4312”
Example 2:
Input: s = "1234"
Output: "None"
Explanation: "1234" is sorted in
ascending order, hence "None".
Your Task:
You dont need to read input or print anything. Complete the function prevPermutation() which takes string s as input parameter and returns lexicographically previous permutation of s and if there is no lexicographically previous permutation of s, it returns "None".
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |s| ≤ 10^{3}

见题面

见题面