DRW New Grad Software Engineer Interview Experience — A Greedy String-Parity Coding Problem

I ran into a greedy string problem.

Given a string digits made up only of the characters '1' and '2', representing a positive integer, you can delete zero or more characters. After deleting, the requirements are:

• The remaining '1's must appear an even number of times.
• The remaining '2's must also appear an even number of times.
• Subject to those two conditions, the resulting integer should be as large as possible.

Note that you can only delete characters — you can't change the relative order of the ones that remain. For example:

• 121212 -> 2121
• 2121122 -> 221122
• 1111 -> 1111

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

The problem itself isn't that hard — the main difficulty is figuring out, greedily, which character to delete when a digit shows up an odd number of times, so that the final number ends up as large as possible. At first I thought you could just delete the first '1' or the last '2', but you still have to carefully think through a bunch of different arrangement cases.