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.