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:
Example 2:
Example 3:
Solution
Here we can use Stack to keep track of the visited characters, Start iterating number from left and push it to the Stack, We can get minimum number if current digit is smaller then the previous digit.
For Example,
Iterate above approach till
Code
0 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 |
public class RemoveKDigits { public String removeKdigits(String num, int k) { int digits = num.length() - k; char[] stack = new char[num.length()]; //Character arr as Stack int topInd = 0; for (int i = 0; i < num.length(); ++i) { char c = num.charAt(i); while (topInd > 0 && stack[topInd - 1] > c && k > 0) { topInd -= 1; k -= 1; } stack[topInd++] = c; } // find the index of first non-zero digit int idx = 0; while (idx < digits && stack[idx] == '0') idx++; return idx == digits ? "0" : new String(stack, idx, digits - idx); } public static void main(String[] args) { RemoveKDigits removeKDigObj=new RemoveKDigits(); System.out.println(removeKDigObj.removeKdigits("1432219", 3)); } } |
Output
Complexity Analysis
Time complexity: O(N).Space Complexity: O(N).
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.