## Largest Number After Digit Swaps by Parity

• Time:O(\log \texttt{num})
• Space:O(\log \texttt{num})

## C++

``````class Solution {
public:
int largestInteger(int num) {
const string s = to_string(num);
int ans = 0;
// maxHeap[0] := odd digits
// maxHeap[1] := even digits
vector<priority_queue<int>> maxHeap(2);

for (const char c : s) {
const int digit = c - '0';
maxHeap[digit & 1].push(digit);
}

for (const char c : s) {
const int i = c - '0' & 1;
ans *= 10;
ans += maxHeap[i].top(), maxHeap[i].pop();
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int largestInteger(int num) {
final String s = String.valueOf(num);
int ans = 0;
// maxHeap[0] := odd digits
// maxHeap[1] := even digits
Queue<Integer>[] maxHeap = new Queue[2];

for (int i = 0; i < 2; ++i)
maxHeap[i] = new PriorityQueue<>(Comparator.reverseOrder());

for (final char c : s.toCharArray()) {
final int digit = c - '0';
maxHeap[digit & 1].offer(digit);
}

for (final char c : s.toCharArray()) {
final int i = c - '0' & 1;
ans = (ans * 10 + maxHeap[i].poll());
}

return ans;
}
}
``````

## Python

``````class Solution:
def largestInteger(self, num: int) -> int:
s = str(num)
ans = 0
# maxHeap[0] := odd digits
# maxHeap[1] := even digits
maxHeap = [[] for _ in range(2)]

for c in s:
digit = ord(c) - ord('0')
heapq.heappush(maxHeap[digit & 1], -digit)

for c in s:
i = ord(c) - ord('0') & 1
ans = (ans * 10 - heapq.heappop(maxHeap[i]))

return ans
``````