aakarshmadhavan's blog

Remove k digits from number
By aakarshmadhavan, history, 6 years ago, In English 

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

If there are no zeros, you can use a greedy strategy: Go left to right and look at each digit one by one. You remove a digit if it is the last digit or if it is larger than the next digit. After removing a digit, you go back one step and look at the previous digit again. This is so that in a case like 22221 you will remove all of the 2's before removing the 1.

For example with 1432219:

  • At (1)432219, you don't remove the 1.
  • At 1(4)32219, you remove the 4 because it is larger than the next digit, 3.
  • At (1)32219, you don't remove the 1.
  • At 1(3)2219, you remove the 3.
  • At (1)2219, you don't remove the 1.
  • At 1(2)219, you don't remove the 2.
  • At 12(2)19, you remove the 2 because it's larger than the next digit.
  • At 1(2)19, you remove the 2 again.
  • At (1)19, you don't remove.
  • At 1(1)9, you don't remove.
  • At 11(9), you remove the 9 because it's the last digit.

Etc., so for 1432219 and k=1,2,... you get 1432219, 132219, 12219, 1219, 119, 11, 1.

If there are zeros in the input, I'm not yet sure if this strategy works without modification or if there are some corner cases.

Edit: I think this strategy should work without changes even when the input contains zeros.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain why the greedy strategy works for the case with no zeros?

    I was thinking of removing largest digit in every iteration, O(N^2) time, it seems yours is O(N)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Let's say you have ...65.... Removing some digit after the 6 will give you ...6..., but removing the 6 results in ...5..., which is lexicographically smaller.

      You need to find the earliest digit that is larger than the following digit, which is what the greedy algorithm does. You're right that it's O(n).

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Removing the largest digit doesn't work. If you have 1219, removing the nine gives 121, which is larger than the optimal 119.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Simple greedy, find smallest number that can be first, then second, and so on. For this you can use segment tree to find min, or you can store each occurence of digits and erase them one by one.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

see here: http://junhaolin.com/Leetcode_Remove_K_Digits.html

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Explaining what the lines of code do instead of writing down the code ;)

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

here is the simple implementation using stack. The algorithm is already explained in the above comments.

Spoiler
→ Reply