Remove K Digits

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.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Analysis:
-- This is asking to remove K numbers from a number and result value should be smallest
-- to make a number smallest, make sure the next number moving up should be smaller than the one being removed.
--scan from left to right, keep removing the one bigger than its right neighbour
--after a number is removed, we need to compare its left neighbour and right neighbour
--if number is already in ascending order, we need to remove right most numbers-- right most non-zero numbers

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

public class Solution { public String removeKdigits(String num, int k) { Objects.requireNonNull(num); if(k==0)return num; if(num.length()==1 && k==1)return "0"; int pre=0,cur=1; StringBuilder sb = new StringBuilder(num); //from left to right, delete character that is bigger than right neighbor while(k>0 && cur<sb.length()){ if(sb.charAt(cur)<sb.charAt(pre)){ sb.deleteCharAt(pre); if(pre>0){ //we now need to compare the left and right neighbors of the one being removed pre--; cur--; } k--; }else{ //moving forward if element in cur is greater than element at pre cursor pre=cur; cur++; } } //last pass might not remove enough characters int rightPosition = sb.length()-1; //then need to go through it from right to left and remove the right most non-zero one while(k>0 && rightPosition>=0){ if(sb.charAt(rightPosition)!='0'){ sb.deleteCharAt(rightPosition); k--; } rightPosition--; } //remove leading 0s while(sb.length()>0 && sb.charAt(0)=='0'){ sb.deleteCharAt(0); } return (sb.length()==0?"0":sb.toString()); } }