Quick Overview

Delete digits while preserving order to maximize a number whose counts of both ones and twos are even, with linear-time handling of long strings.

Maximize a Digit Subsequence with Even Counts of Ones and Twos

Company: DRW

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: HR Screen

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: `""`

Overview: Delete digits while preserving order to maximize a number whose counts of both ones and twos are even, with linear-time handling of long strings.

Read the full DRW Software Engineer interview experience this question came from

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.

Constraints

  • 1 <= len(digits) <= 200000.
  • Every character of `digits` is `1` or `2`.
  • The returned string must be a subsequence of `digits` (the relative order of kept characters is preserved).
  • In the returned string the count of `1` must be even and the count of `2` must be even; zero is even.
  • If no nonempty valid subsequence exists, return the empty string `""`.
  • Return a string; do not convert the whole input to a machine-sized integer.
  • The intended solution runs in O(n) time, where n is the input length; O(n) output storage is permitted.

Examples

Input: ('1',)

Expected Output: ''

Explanation: Minimum length: one '1' is an odd count, so it must be deleted and nothing valid and nonempty remains.

Input: ('2',)

Expected Output: ''

Explanation: Minimum length: one '2' is an odd count, so it must be deleted and the result is empty.

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.

Loading coding console...

Show the approach

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)