Given an integer S. Find the largest even number that can be formed by rearranging the digits of S.
Note: In case the number does not contain any even digit then output the largest odd number possible.
Example 1:
Input:
S = "1324"
Output: "4312"
Explanation: Largest even number: 4312
Example 2:
Input:
S = "3555"
Output: "5553"
Explanation: No even number possible,
So we'll find largest odd number.
Your Task:
You don't need to read input or print anything. Your task is to complete the function LargestEven() which takes the string S as inputs representing the integer and returns the answer.
Expected Time Complexity: O(|S| * log |S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}
S contains only digits from '0' to '9'.

见题面

见题面