Given a number N, and a number K, find the minimum number that can be formed by deleting K digits. The order of the digits should not be changed.

For example consider N = 234987, K = 2, we can remove 9,8 and the resulting number is **2347**.

The solution is based on the following observation, consider the above case.

Let us delete a digit from 234987

Deleted Digit – Result

—————————

2 – 34987

3 – 24987

4 – 23987

**9 – 23487**

8 – 23497

7 – 23498

If we remove 9 we will get the minimum number. Observe that in the given number, 9 is the first digit which is greater than the next digit.

What if all the digits are in ascending order?

Let us walk through an example.

N = 12345, K = 3. If we remove 4,5 we will get the minimum number. The observation is that we need to keep on removing right-most digits in this case.*[This is a re-post after correcting my incorrect approach. Thanks to Jeff Senecal for pointing out the mistake.] *

Here is the C++ implementation of the above approach.