LeetCode Solutions Blog

Largest Number After Digit Swaps by Parity

Number: 2327

Difficulty: Easy

Paid? No

Problem Description

Given a positive integer num, you can swap any two digits that share the same parity (i.e. both odd digits or both even digits). The task is to return the largest possible number you can obtain by performing any number of allowed swaps.

Key Insights

Separate the digits of the number based on their parity (odd and even).
Since only digits of the same parity may be swapped, sort the odd digits and even digits independently in descending order.
Reconstruct the number by replacing each digit with the next available largest digit from its corresponding parity group.

Space and Time Complexity

Time Complexity: O(D log D) where D is the number of digits (due to sorting)
Space Complexity: O(D), to store the separated lists of odd and even digits

Solution

The solution involves:

Converting the integer into a list of its digits.
Creating separate lists for odd and even digits.
Sorting both lists in descending order since we want to place the biggest digit possible in each digit's position.
Rebuilding the number by iterating over the original digits and replacing each digit with the next largest digit from the corresponding sorted list (depending on whether it is odd or even).
This approach ensures that, while we respect the parity constraint, we also maximize the number digit by digit.

Code Solutions

# Function to find largest number after allowed digit swaps by parity
def largestInteger(num):
    # Convert number to a list of characters (digits)
    digits = list(str(num))
    
    # Separate odd and even digits
    odds = [d for d in digits if int(d) % 2 == 1]
    evens = [d for d in digits if int(d) % 2 == 0]
    
    # Sort the odd and even lists in descending order
    odds.sort(reverse=True)
    evens.sort(reverse=True)
    
    # Initialize indices for odd and even lists
    odd_index, even_index = 0, 0
    
    # Build the result by selecting the next largest available digit for each position
    for i, d in enumerate(digits):
        if int(d) % 2 == 1:
            # Replace odd digit with the next largest odd digit
            digits[i] = odds[odd_index]
            odd_index += 1
        else:
            # Replace even digit with the next largest even digit
            digits[i] = evens[even_index]
            even_index += 1
            
    # Join the list back into a single number string and convert to integer
    return int(''.join(digits))

# Example usage:
print(largestInteger(1234))  # Output: 3412
print(largestInteger(65875)) # Output: 87655