DRW New Grad Software Engineer Interview Experience — A Greedy Deletion Problem on a String of 1s and 2s

I got a string greedy problem:

Given a string digits made up only of '1' and '2', which represents a positive integer. You can delete 0 or more characters from it, and after the deletion: the number of remaining '1's must be even; the number of remaining '2's must also be even; and, while satisfying those first two conditions, the final integer should be as large as possible.

Note that you can only delete characters. You cannot change the original relative order of the remaining characters.

For example: 121212 -> 2121, 2121122 -> 221122, 1111 -> 1111.

The constraint is N <= 200000, so it should need a solution of around O(N).

The problem itself isn't that hard. The main thing is how to greedily decide, when a digit appears an odd number of times, which occurrence you should actually delete so that the final number is guaranteed to be the largest. At first I felt like just deleting the first 1 / the last 2 would do it, but you still need to think carefully through the cases for the different arrangements.