Maximize a Digit Subsequence with Even Counts of Ones and Twos

Given a string digits containing only 1 and 2, delete zero or more characters so that the remaining count of each digit is even. Preserve the relative order of all remaining characters. Return the remaining string that represents the largest possible integer.

Function Signature

largest_even_count_number(digits: str) -> str

Output Rules

• The output must be a subsequence of digits.
• The count of 1 must be even, and the count of 2 must be even; zero is even.
• Because all digits are nonzero, a longer nonempty result represents a larger integer. For equal lengths, ordinary lexicographic order determines the larger value.
• If no nonempty valid subsequence exists, return "". This explicit convention covers inputs whose only valid result is empty.
• Return a string; do not convert the whole input to a machine-sized integer.

Constraints

• 1 <= len(digits) <= 200000.
• Every character is 1 or 2.
• Your approach should run in O(n) time, where n is the input length, with O(n) output storage permitted.

Examples

Input: digits = "121212"

Output: "2121"

Input: digits = "2121122"

Output: "221122"

Input: digits = "1111"

Output: "1111"

Input: digits = "12"

Output: ""

Largest Number After Making Both Digit Counts Even

You are given a string digits that contains only the characters 1 and 2.

Delete zero or more characters from digits so that, in the remaining string, the number of 1 characters is even and the number of 2 characters is even (zero is even). The characters you keep must stay in their original relative order, so the result is a subsequence of digits.

Among all such subsequences, return the one that represents the largest possible integer, as a string.

Because every digit is nonzero, a longer nonempty result always represents a larger integer than a shorter one; when two candidates have the same length, ordinary lexicographic order decides which is larger. If no nonempty valid subsequence exists, return the empty string "".

Return the answer as a string; do not convert the whole input into a machine-sized integer.

Example 1:

Input: digits = "121212"
Output: "2121"

Explanation: The input has three 1 characters and three 2 characters, so at least one of each must be deleted and no valid result is longer than four characters. Among the four-character candidates, "2121" is the largest.

Example 2:

Input: digits = "2121122"
Output: "221122"

Explanation: The input has three 1 characters and four 2 characters, so exactly one 1 has to be deleted and every valid answer has six characters. Deleting the 1 at index 1 yields "221122", which is larger than "212112" or any other six-character choice.

Hints

1. Every digit is nonzero, so no valid answer has a leading zero: compare candidates by length first and only use lexicographic order to break ties between equally long ones.
2. Only the parity of each digit's count can make a string invalid, which pins down exactly how many characters any optimal answer removes.
3. The two digit values are not symmetric. Removing a character lets the characters after it shift one place to the left, and whether that helps depends on whether the removed digit is the smaller or the larger one.

Approach

Algorithm. Count the '1' characters and the '2' characters. Let c1 and c2 be those counts. Any valid answer keeps an even number of each, so it keeps at most c1 - (c1 % 2) ones and at most c2 - (c2 % 2) twos; that bounds its length by L = c1 - (c1 % 2) + c2 - (c2 % 2). Because every digit is nonzero, no result can have a leading zero, so a longer string always represents a strictly larger integer than a shorter one. Therefore every optimal answer has exactly length L: it deletes exactly one '1' when c1 is odd, exactly one '2' when c2 is odd, and nothing else.

Which occurrence to delete. Consider deleting the '1' at position i versus a later '1' at position j (i < j). The two results share the prefix before i and the suffix after j; the differing middles are X + '1' (delete the earlier one) and '1' + X (delete the later one), where X is the segment strictly between the two positions. If X is all '1' characters the results are equal; otherwise the first position where they differ holds '2' in X + '1' and '1' in '1' + X, so deleting the earlier '1' is at least as good. Hence delete the FIRST '1'. The mirror argument for '2' compares X + '2' with '2' + X: if X contains a '1', '2' + X is larger at the first differing position, so deleting the LATER '2' is at least as good. Hence delete the LAST '2'.

Invariant and independence. Deleting a '2' never changes which '1' is first, and deleting a '1' never changes which '2' is last. So for any fixed choice q of the deleted '2', switching the deleted '1' to the first '1' cannot hurt, and with that '1' fixed, switching the deleted '2' to the last '2' cannot hurt. The pair (first '1', last '2') is therefore jointly optimal, and the scan below is a single pass that skips exactly those positions.

Edge cases. Both counts already even: the input is returned unchanged. c1 odd with c1 == 1 and c2 odd with c2 == 1 (for example "12"): both characters are removed and the result is the empty string, which the statement mandates. A single character input always returns the empty string. Inputs consisting of only one digit type are handled by the same parity rule, since the count of the absent digit is zero, which is even. If c2 is odd there is at least one '2', so the backward scan for the last '2' always finds one.

• Time complexity: O(n)
• Space complexity: O(n)