Largest Even Number

Difficulty: Easy | Acceptance: 69.40% | Paid: No Topics: String

You are given a string num consisting of digits only. Your task is to rearrange the digits of num to form the largest possible even number.

Return the resulting string. If it is impossible to form an even number, return an empty string.

Note that the resulting number may have leading zeros.

Table of Contents

• Examples
• Constraints
• Greedy with Sorting
• Counting Sort Approach

Examples

Example 1

Input: num = "420"
Output: "420"
Explanation: "420" is already the largest even number that can be formed.

Example 2

Input: num = "123"
Output: "312"
Explanation: The largest even number that can be formed is "312".

Example 3

Input: num = "135"
Output: ""
Explanation: It is impossible to form an even number as all digits are odd.

Constraints

- 1 <= s.length <= 100
- s consists only of the characters '1' and '2'.

Greedy with Sorting

Intuition To form the largest even number, we want the largest digits at the front and an even digit at the end. We can sort digits in descending order and then find the smallest even digit to place at the end.

Steps

• Sort the string in descending order
• Find the rightmost (smallest) even digit
• Move that digit to the end
• If no even digit exists, return empty string

class Solution:
    def largestEvenNumber(self, num: str) -> str:
        # Convert to list and sort in descending order
        digits = sorted(num, reverse=True)
        
        # Find the smallest even digit (rightmost even digit)
        even_idx = -1
        for i in range(len(digits) - 1, -1, -1):
            if int(digits[i]) % 2 == 0:
                even_idx = i
                break
        
        # If no even digit found, return empty string
        if even_idx == -1:
            return ""
        
        # Move the even digit to the end
        even_digit = digits.pop(even_idx)
        digits.append(even_digit)
        
        return "".join(digits)

Complexity

• Time: O(n log n) for sorting
• Space: O(n) for storing the character array
• Notes: Simple and intuitive, but sorting takes O(n log n) time

Counting Sort Approach

Intuition Since we only have 10 possible digits (0-9), we can use counting sort to achieve O(n) time complexity. We count the frequency of each digit and then construct the result by placing digits from largest to smallest, ensuring the last digit is even.

Steps

• Count the frequency of each digit (0-9)
• Find the smallest even digit that exists
• Construct the result by placing digits from 9 down to 0
• Use one less of the chosen even digit and place it at the end

class Solution:
    def largestEvenNumber(self, num: str) -> str:
        # Count frequency of each digit
        count = [0] * 10
        for ch in num:
            count[int(ch)] += 1
        
        # Find the smallest even digit that exists
        even_digit = -1
        for d in range(0, 10, 2):  # 0, 2, 4, 6, 8
            if count[d] > 0:
                even_digit = d
                break
        
        # If no even digit found, return empty string
        if even_digit == -1:
            return ""
        
        # Use one occurrence of the even digit for the end
        count[even_digit] -= 1
        
        # Build the result from largest to smallest digit
        result = []
        for d in range(9, -1, -1):
            result.append(str(d) * count[d])
        
        # Append the even digit at the end
        result.append(str(even_digit))
        
        return "".join(result)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) for the count array (fixed size 10) plus O(n) for the result
• Notes: Optimal solution with linear time complexity