Maximize a Digit Subsequence with Even Counts of Ones and Twos

Problem Statement

You are given a string digits consisting entirely of the characters '1' and '2'. The string represents a positive decimal integer.

You can delete zero or more characters from digits to form a subsequence such that:

1. The count of '1's in the resulting string is even.
2. The count of '2's in the resulting string is even.
3. The resulting integer is as large as possible.

Return the resulting string. If the optimal result is empty (all characters removed), return the empty string "".

Note: Since all digits are positive ('1' and '2'), any integer with more digits is strictly greater than an integer with fewer digits. If two candidates have the same length, the larger integer is the one that is lexicographically larger.

Function Signature

def max_even_subsequence(digits: str) -> str:
    pass

Input and Output

• Input: A string digits where 1 <= len(digits) <= 2 * 10^5 and digits[i] in {'1', '2'}.
• Output: A string representing the maximum valid number.

Examples

Example 1

Input: digits = "21121"
Output: "2112"
Explanation: 
- Original counts: two '2's (even), three '1's (odd).
- To make both counts even while maximizing the number of digits, we must delete exactly one '1'.
- Options after deleting one '1': "112" (deleting first '2' is invalid), deleting first '1' gives "212", deleting second '1' gives "212", deleting third '1' gives "2112".
- "2112" has length 4 and is the largest valid number.

Example 2

Input: digits = "12122"
Output: "2122"
Explanation: 
- Original counts: two '1's (even), three '2's (odd).
- We must remove exactly one '2'.
- Removing the first '2' yields "1122".
- Removing the second '2' yields "1212".
- Removing the third '2' yields "1212".
- Wait, removing the first '1' is not allowed since '1's are already even.
- Removing the first '2' gives "1122", removing the second gives "1212". Here "1212" > "1122", so "1212" is optimal.

Example 3

Input: digits = "12"
Output: ""
Explanation:
- Original counts: one '1' (odd), one '2' (odd).
- We must remove one '1' and one '2', leaving an empty string "".

Constraints

• 1 <= len(digits) <= 2 * 10^5
• digits[i] in {'1', '2'} for all 0 <= i < len(digits)
• Time complexity must be O(n) where n = len(digits).
• Auxiliary space complexity should be O(n) to store the result.