Largest Even Number - Solution & Explanation

Problem Overview: You are given a string containing numeric digits. Rearrange the digits to form the largest possible number that is even. If no arrangement produces an even number, return an empty string. The key constraint: the final digit must be even (0, 2, 4, 6, or 8).

Approach 1: Permutation Brute Force (O(n!))

The most direct idea is to generate every permutation of the digits and check which permutations form an even number. For each permutation, verify that the last digit is even and keep track of the maximum numeric value. This guarantees the correct answer because it explores the entire search space. However, generating all permutations takes O(n!) time and O(n) recursion space, which becomes infeasible even for moderately sized strings. This approach mainly helps demonstrate the core constraint: the last digit determines whether the number is even.

Approach 2: Greedy Digit Placement (Sorting) (O(n log n))

A much better strategy uses a greedy observation: to maximize the number, the digits should appear in descending order, but the final digit must be even. First scan the string and collect all digits. Identify the smallest even digit because placing the smallest even digit at the end preserves larger digits in more significant positions. Sort the remaining digits in descending order and append the chosen even digit at the end. Sorting dominates the cost, resulting in O(n log n) time with O(n) space for storing digits. This greedy construction ensures the number remains even while maximizing its overall value.

Approach 3: Counting Digits Optimization (O(n))

Since digits range only from 0–9, you can avoid sorting by counting digit frequencies. Iterate through the string once and maintain a frequency array of size 10. Choose the smallest even digit with a non-zero count for the final position and decrement its count. Then rebuild the number by appending digits from 9 down to 0 according to their frequencies, and finally append the selected even digit. The counting pass and reconstruction both take linear time, giving O(n) time and O(1) auxiliary space. This approach leverages simple string processing and basic greedy reasoning.

Recommended for interviews: The greedy approach is typically expected. It shows that you recognize the key constraint (the last digit controls parity) and can structure the number to maximize higher place values. Mentioning the brute force permutation approach shows problem exploration, but implementing the greedy or counting-based method demonstrates stronger algorithmic thinking and efficient array manipulation.