Largest Number From a 1-and-2 Digit String With Even Counts of Each Digit
Company: DRW
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: HR Screen
You are given a string `digits` consisting only of the characters `'1'` and `'2'`; it represents a positive integer. You may delete zero or more characters from `digits`. The characters you keep stay in their original relative order and cannot be changed or rearranged.
After the deletions, the remaining string must satisfy both of these conditions:
1. The number of remaining `'1'` characters is even.
2. The number of remaining `'2'` characters is even.
Among all remaining strings that satisfy both conditions, return the one that represents the largest integer.
### Function Signature
```python
def largest_even_count_number(digits: str) -> str:
```
### Rules
- Zero is an even count. A result with no `'1'` characters satisfies the first condition, and a result with no `'2'` characters satisfies the second.
- Compare results as integers. Because every digit is nonzero, a longer result is larger than a shorter one, and among results of equal length the lexicographically larger string is larger.
- If no nonempty string satisfies both conditions, return the empty string `""`. For example, `digits = "12"` returns `""`. This empty-result rule is an explicit convention for this exercise.
- Different sets of deleted positions can leave the same string. Only the resulting string is returned, so the answer is unique.
### Constraints
- `1 <= len(digits) <= 200000`.
- Every character of `digits` is `'1'` or `'2'`.
- The represented integer can have up to 200000 digits, far beyond the 64-bit range, so the input and the output are strings. Do not convert them to a numeric type.
- Aim for a solution that runs in roughly linear time in `len(digits)`.
### Examples
**Example 1**
```text
Input: digits = "121212"
Output: "2121"
```
The input has three `'1'` characters and three `'2'` characters, so at least one of each must be deleted. Among the length-4 results with two of each digit, `"2121"` is the largest; `"2211"` cannot be formed without reordering.
**Example 2**
```text
Input: digits = "2121122"
Output: "221122"
```
The input has three `'1'` characters and four `'2'` characters. Deleting the `'1'` at index 1 leaves `"221122"`; deleting the `'1'` at index 3 or index 4 instead leaves the smaller `"212122"`.
**Example 3**
```text
Input: digits = "1111"
Output: "1111"
```
Both counts are already even (four `'1'` characters and zero `'2'` characters), so nothing is deleted.
Overview: Given a string of 1s and 2s that represents a positive integer, delete characters so the remaining counts of both digits are even, keeping the original order, and return the largest number that can remain. The problem tests careful case analysis of which digit occurrences to remove and efficient string handling for inputs up to 200,000 characters.
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'. It represents a positive integer.
You may delete zero or more characters from `digits`. The characters you keep stay in their original relative order and cannot be changed or rearranged.
After the deletions, the remaining string must satisfy both of these conditions:
1. The number of remaining '1' characters is even.
2. The number of remaining '2' characters is even.
Among all remaining strings that satisfy both conditions, return the one that represents the largest integer.
Rules:
- Zero is an even count. A result with no '1' characters satisfies the first condition, and a result with no '2' characters satisfies the second.
- Compare results as integers. Because every digit is nonzero, a longer result is larger than a shorter one, and among results of equal length the lexicographically larger string is larger.
- If no nonempty string satisfies both conditions, return the empty string "". For example, digits = "12" returns "". This empty-result rule is an explicit convention for this exercise.
- Different sets of deleted positions can leave the same string. Only the resulting string is returned, so the answer is unique.
- The represented integer can have up to 200000 digits, which is far beyond 2^31 - 1 and also beyond the 64-bit range, so the input and the returned value are strings. Do not convert them to a numeric type.
Example 1:
Input: digits = "121212"
Output: "2121"
The input has three '1' characters and three '2' characters, so at least one of each must be deleted. Among the length-4 results with two of each digit, "2121" is the largest; "2211" cannot be formed without reordering.
Example 2:
Input: digits = "2121122"
Output: "221122"
The input has three '1' characters and four '2' characters. Deleting the '1' at index 1 leaves "221122"; deleting the '1' at index 3 or index 4 instead leaves the smaller "212122".
Constraints
- 1 <= len(digits) <= 200000
- Every character of digits is '1' or '2'.
- The represented integer can have up to 200000 digits, far beyond 2^31 - 1 and also beyond the 64-bit range, so digits and the returned value are strings; do not convert them to a numeric type.
- The returned value is a string containing only '1' and '2' characters, and it may be empty.
- Aim for a solution that runs in roughly linear time in len(digits).
Examples
Input: ('1',)
Expected Output: ''
Explanation: Minimum length. One '1' is an odd count, so it must be deleted; no nonempty result qualifies, so the convention returns the empty string.
Input: ('2',)
Expected Output: ''
Explanation: Minimum length with the other digit: the single '2' is an odd count and must go, leaving the empty string.
Hints
- Only the parity of each digit's count matters. Work out what the parity of the number of '1' characters and the parity of the number of '2' characters force you to delete.
- Deleting a single character changes exactly one of the two parities, and since no digit is zero, a longer result always represents a larger integer than a shorter one.
- When you are forced to drop one copy of a digit, every candidate result has the same length, so compare them lexicographically: what follows the dropped copy decides which choice is best.