Problem Brief

Swap Parity

INTERNOA

Given a number num, two adjacent digits can be swapped if their parity is the same, that is, both are odd or both are even. For example, (5,9) have the same parity, but (6,9) do not.

Find the largest number that can be created. The swap operation can be applied any number of times.

Function Description

Complete the function getLargestNumber in the editor.

getLargestNumber has the following parameter:

string num: a string of digits

Returns

string: the largest number that can be created

1Example 1

Input

num = "7596801"

Output

"9758601"

Explanation

Let num = "7596801".

Swap 5 and 9 -> "7956801"
Swap 7 and 9 -> "9756801"
Swap 6 and 8 -> "9758601"

It can be proven that the largest value possible is "9758601".

2Example 2

Input

num = "0082663"

Output

"8662003"

Explanation

Zero is even parity, so swaps can be made until the digits are arranged as shown.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ length of num ≤ 10^5
num consists of digits 0-9 only.