Katkat
Back

Largest Number From a 1-and-2 Digit String With Even Counts of Each Digit

DRWSoftware Engineer · HR Screen
MediumSoftware EngineerHR ScreenCoding & Algorithms

Last updated

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.

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

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

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".

Example 3

Input: digits = "1111"
Output: "1111"

Both counts are already even (four '1' characters and zero '2' characters), so nothing is deleted.