Remove k digits from number

Revision en3, by aakarshmadhavan, 2018-07-14 01:21:33

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. Length of number at most 10002 and is length will be >= k. Num does not contain leading 0's (ie 0200) Input 1: num = "10200", k = 1 Output: "200" ----> Remove leading 1 and the number is 0200 = 200 (cant have leading 0 in answer) Input 2: num = "1432219", k = 3 Output: "1219"----> Remove 3 digits {4, 3, 2} to form "1219" which is the smallest

I think BFS can work but its a pretty shitty solution to use BFS (and it is edge-casey)

I am thinking of either greedy or dynamic programming. I am horrible at greedy and recognizing it. Can anyone help me out here?

Thank you all

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English aakarshmadhavan 2018-07-14 01:21:33 15 Tiny change: '02 and is >= k. Num' -> '02 and is length will be >= k. Num'
en2 English aakarshmadhavan 2018-07-14 01:20:58 3
en1 English aakarshmadhavan 2018-07-14 01:20:41 760 Initial revision (published)