Just do it greedily. If you can delete numbers so that you get a 9 at the front then do it, if not try with an 8, etc. Then you move on to selecting the second most significant digit, etc. You just have to figure out how to do it efficiently ie better than O(nk) complexity, which can be done in various ways. ;)

this problem can be solved using dynammic programming with a complexity of O(N*10) in worst case let us maintain a DP[10][N] (N denotes the length of the number) table where DP[i][j] represents the index of the first occurence of digit i in the range from j to N. Now starting from the first index (MSB) you can check what maximum digit you can get at this position with the available range of K. this way you can move forward filling each position. Can you provide link to the above problem :).

The problem is solvable in O(N).
Instead of directly delete K digits, we can try to find the biggest number with N-K digits. This can be done with simple greedy. Let the string be s[1..n], for the first digit, pick the biggest one in s[1..n-k+1], suppose you find it first at index i1, then the range we should consider for the second digit is s[i1+1..n-k+2], then you got i2, .etc...
Observing that these ranges are monotonic, a deque is enough, or you can build a RMQ sparse table, or a Segment tree.

We can take a array of length 10 (0-9). Each of its index will represent digit and value within that array index will represent how many times this digit was repeated in original number. For digits K, we travel through this array and keep only those values in this array that add up to K from index 0 to 9, rest values we can equate to 0. We again scan original number left to right, For every digit we check if we it has non-zero value present in our aux array if so, we will skip this digit while forming our answer number and decrement the count of array value for that digit by 1. Complexity, O(n).

Anyway, another question: Does this problem available on Codeforces?