# Largest Number After Digit Swaps by Parity
**Difficulty:** EASY
[External](https://leetcode.com/problems/largest-number-after-digit-swaps-by-parity)
Canonical: https://scaleengineer.com/dsa/problems/largest-number-after-digit-swaps-by-parity
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Heap (Priority Queue)
**Companies:** [ZScaler](https://scaleengineer.com/companies/zscaler)
---
## Problem
You are given a positive integer `num`. You may swap any two digits of `num` that have the same **parity** (i.e. both odd digits or both even digits).

Return _the **largest** possible value of_ `num` _after **any** number of swaps._

**Example 1:**

**Input:** num = 1234
**Output:** 3412
**Explanation:** Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

**Example 2:**

**Input:** num = 65875
**Output:** 87655
**Explanation:** Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

**Constraints:**

* `1 <= num <= 109`

# Approaches
## Separate, Sort, and Reconstruct
The core idea is that we can freely swap any two digits of the same parity. This means we can arrange all the odd digits in any order among their original positions, and similarly for the even digits. To get the largest number, we should place the largest digits at the most significant positions (leftmost). This can be achieved by sorting the odd and even digits separately in descending order and then reconstructing the number by placing the sorted digits back into their original parity-based positions.
**Time:** O(D log D), where D is the number of digits in `num`. The dominant operation is sorting the lists of digits. Converting the number to/from a string and iterating through it takes O(D) time. · **Space:** O(D), where D is the number of digits in `num`. This space is used to store the string representation of the number, the two lists of digits, and the `StringBuilder` for the result.
**Pros:** Relatively simple to understand and implement.; Correctly solves the problem by identifying the core property of swappable groups.
**Cons:** Not the most optimal solution in terms of time complexity, as sorting can be done more efficiently for a small, fixed range of values (digits 0-9).
### Explanation
This approach involves separating the digits of the number into two groups based on their parity (odd or even). Each group of digits can be rearranged arbitrarily among themselves. To maximize the final number, we should use the largest available digits in the most significant positions. Therefore, we sort both the odd and even digits in descending order. Then, we reconstruct the number by iterating through the original number's digit positions. For each position, we determine its original parity and place the next largest digit from the corresponding sorted list.

For example, with `num = 1234`:
1.  Original digits: `1, 2, 3, 4`. Parity pattern: `Odd, Even, Odd, Even`.
2.  Odd digits: `1, 3`. Even digits: `2, 4`.
3.  Sorted odd digits (descending): `3, 1`. Sorted even digits (descending): `4, 2`.
4.  Reconstruct:
    - 1st position (Odd): Use largest odd digit `3`.
    - 2nd position (Even): Use largest even digit `4`.
    - 3rd position (Odd): Use next largest odd digit `1`.
    - 4th position (Even): Use next largest even digit `2`.
5.  Result: `3412`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int largestInteger(int num) {
        String s = String.valueOf(num);
        List<Character> oddDigits = new ArrayList<>();
        List<Character> evenDigits = new ArrayList<>();

        for (char c : s.toCharArray()) {
            int digit = c - '0';
            if (digit % 2 == 0) {
                evenDigits.add(c);
            } else {
                oddDigits.add(c);
            }
        }

        // Sort in descending order
        Collections.sort(oddDigits, Collections.reverseOrder());
        Collections.sort(evenDigits, Collections.reverseOrder());

        StringBuilder result = new StringBuilder();
        int oddIndex = 0;
        int evenIndex = 0;

        for (char c : s.toCharArray()) {
            int digit = c - '0';
            if (digit % 2 == 0) {
                result.append(evenDigits.get(evenIndex++));
            } else {
                result.append(oddDigits.get(oddIndex++));
            }
        }

        return Integer.parseInt(result.toString());
    }
}
```
### Algorithm
- Convert the input number `num` into a string `s`.
- Create two separate lists: `oddDigits` and `evenDigits`.
- Iterate through the characters of `s`. If a digit is odd, add it to the `oddDigits` list. If it's even, add it to the `evenDigits` list.
- Sort the `oddDigits` list in descending order.
- Sort the `evenDigits` list in descending order.
- Initialize two pointers, `oddIndex = 0` and `evenIndex = 0`.
- Create a `StringBuilder` to construct the result.
- Iterate through the characters of the original string `s` again. For each character:
  - If the original digit was odd, append the digit from `oddDigits` at `oddIndex` to the result and increment `oddIndex`.
  - If the original digit was even, append the digit from `evenDigits` at `evenIndex` to the result and increment `evenIndex`.
- Convert the `StringBuilder` back to an integer and return it.

## Optimized Sorting with Counting Sort
This approach improves upon the previous one by using a more efficient sorting algorithm suitable for the problem's constraints. Since the values to be sorted are single digits (0-9), we can use Counting Sort, which has a linear time complexity. We count the occurrences of each odd and even digit and then reconstruct the number by picking the largest available digits of the correct parity for each position.
**Time:** O(D), where D is the number of digits in `num`. Converting to a string, populating the count arrays, and reconstructing the number each take O(D) time. The inner loops for finding the next digit run a constant number of times, so the total time complexity is linear. · **Space:** O(D), where D is the number of digits in `num`. We use O(1) space for the count arrays (constant size). The space is dominated by storing the string representation of the number (`O(D)`) and the `StringBuilder` for the result (`O(D)`).
**Pros:** Most efficient approach with linear time complexity.; Avoids the overhead of comparison-based sorting.
**Cons:** Slightly more complex to implement than the direct sorting approach due to managing frequency arrays.
### Explanation
Instead of a general-purpose comparison sort, we can use a more specialized and faster algorithm given that we are only sorting digits. Counting sort is ideal here. We can use two frequency arrays, one for odd digits and one for even digits, to count the occurrences of each.

After counting, we reconstruct the number. We iterate through the original number's positions one by one. If a position originally held an even number, we find the largest even digit we have in our frequency map, append it to our result, and decrement its count. We do the same for positions that originally held an odd number. This ensures that the largest digits are placed in the most significant positions possible while respecting the parity constraints.

```java
class Solution {
    public int largestInteger(int num) {
        String s = String.valueOf(num);
        int[] oddCounts = new int[10];
        int[] evenCounts = new int[10];

        for (char c : s.toCharArray()) {
            int digit = c - '0';
            if (digit % 2 == 0) {
                evenCounts[digit]++;
            } else {
                oddCounts[digit]++;
            }
        }

        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            int digit = c - '0';
            if (digit % 2 == 0) { // Position requires an even digit
                // Find the largest available even digit
                for (int d = 8; d >= 0; d -= 2) {
                    if (evenCounts[d] > 0) {
                        result.append(d);
                        evenCounts[d]--;
                        break;
                    }
                }
            } else { // Position requires an odd digit
                // Find the largest available odd digit
                for (int d = 9; d >= 1; d -= 2) {
                    if (oddCounts[d] > 0) {
                        result.append(d);
                        oddCounts[d]--;
                        break;
                    }
                }
            }
        }
        return Integer.parseInt(result.toString());
    }
}
```
### Algorithm
- Convert `num` to a string `s`.
- Create two frequency arrays, `oddCounts` and `evenCounts`, of size 10, initialized to zeros.
- Iterate through each character `c` in `s`:
  - Let `digit` be the integer value of `c`.
  - If `digit` is even, increment `evenCounts[digit]`.
  - Otherwise, increment `oddCounts[digit]`.
- Initialize a `StringBuilder` `result`.
- Iterate through each character `c` in `s` again:
  - Let `digit` be the integer value of `c`.
  - If `digit` is even (i.e., the original position held an even number):
    - Find the largest `d` from 8 down to 0 (by 2s) such that `evenCounts[d] > 0`.
    - Append `d` to `result` and decrement `evenCounts[d]`.
    - Break the inner search loop.
  - If `digit` is odd:
    - Find the largest `d` from 9 down to 1 (by 2s) such that `oddCounts[d] > 0`.
    - Append `d` to `result` and decrement `oddCounts[d]`.
    - Break the inner search loop.
- Convert `result` to an integer and return it.

# Solutions
### Java

```java
class Solution {
public
  int largestInteger(int num) {
    int[] cnt = new int[10];
    int x = num;
    while (x != 0) {
      cnt[x % 10]++;
      x /= 10;
    }
    x = num;
    int ans = 0;
    int t = 1;
    while (x != 0) {
      int v = x % 10;
      x /= 10;
      for (int y = 0; y < 10; ++y) {
        if (((v ^ y) & 1) == 0 && cnt[y] > 0) {
          cnt[y]--;
          ans += y * t;
          t *= 10;
          break;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int largestInteger(int num) {
    vector<int> cnt(10);
    int x = num;
    while (x) {
      cnt[x % 10]++;
      x /= 10;
    }
    x = num;
    int ans = 0;
    long t = 1;
    while (x) {
      int v = x % 10;
      x /= 10;
      for (int y = 0; y < 10; ++y) {
        if (((v ^ y) & 1) == 0 && cnt[y] > 0) {
          cnt[y]--;
          ans += y * t;
          t *= 10;
          break;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestInteger(self, num: int) -> int: cnt = Counter() x = num while x: x, v = divmod(x, 10) cnt[v] += 1 x = num ans = 0 t = 1 while x: x, v = divmod(x, 10) for y in range(10): if ((v ^ y) & 1) == 0 and cnt[y]: ans += y * t t *= 10 cnt[y] -= 1 break return ans

```