Given string num representing a non-negative integer num, and an integer k, return the smallest possible
integer after removing k digits from num.
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.
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.
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Constraints:
- 1 <= k <= num.length <= 105
- num consists of only digits.
- num does not have any leading zeros except for the zero itself.
Contents
- Solution 1 - Using a Stack
Let's understand the intution behind this approach using some examples, since we do not know which order the numbers are in, and choosing what digits to remove
will result in smallest number possible.
For example, consider num="987321" and k=2, as we can clearly see remove the leading two digits 9 and 8 will give
us the smallest number possible 7321 after removing these 2 digits.
Say if num="978321" and k=2, we still can remove the leading two digits 9 and 8 to get
the smallest number, but unlike the above example, these two digits are not next to each other, but there is only one number in between and
after removing the first choice 9 we still have choice to remove one more digit since k=2, and we can choose either 7 or 8,
so we can choose 8 to remove to get the smallest number 7321.
Let's look at one more exaple, similar to above example say if the num="9758321" (added digit 5 between 7 and 8),
in this case, removing the same digits like above two example will not result in smallest number, because there are two smaller numbers in between
9 and 8 which are 7 and 5, say we remove 9 and 8, we will get 75321, but if we remove 9 and 7
we will get 58321 which is smaller.
As you can see from above examples, removing just a bigger digit doesn't always guarantee a smallest number
Let's look at one more example, num="1432219" and k=3, here removing the highlighted numbers 4,3, and 2 will gives us the smallest number
1432219
If you observe a pattern in last two examples above, we are trying to remove digits from last side if they are not in monotomically decreasing order with atmost
k digits.
In the above example, first digit is 1, then the next digit is 4, is 1>4 ? no, so we don't do anything,
then the next digit is 3, is 4 > 3 ? yes, so remove 4, similarly we will remove the next two digits 3 and 2 since they also satisfy the condition
that the number before that is either bigger or same.
In this implementation, we are going apply above logic using a Stack and construct a monotomically decreasing stack with atmost k removal operations.
import java.util.Stack;
public class RemoveKDigits {
static String removeKDigits(String num, int k) {
Stack<Character> stack = new Stack<>();
for(char c : num.toCharArray()) {
while(!stack.isEmpty() && k>0 && stack.peek()>c) {
k--;
stack.pop();
}
stack.push(c);
}
while(k>0) { // in case if k is still not zero, for example if the input string is already in sorted order 1234567
k--;
stack.pop();
}
//find the first non-zero leading digit, this is to remove all leading zero
int nonZeroLeadingIndex = 0;
while(nonZeroLeadingIndex<stack.size()) {
if(stack.get(nonZeroLeadingIndex)> '0'){
break;
}
nonZeroLeadingIndex++;
}
StringBuilder sb = new StringBuilder();
for(int i=nonZeroLeadingIndex; i<stack.size();i++) {
sb.append(stack.get(i));
}
return sb.isEmpty() ? "0" : sb.toString();
}
public static void main(String[] args) {
System.out.println(removeKDigits("00000001432219", 3));
System.out.println(removeKDigits("1432219", 3));
System.out.println(removeKDigits("10200", 1));
}
}
Complexity Analysis:
Time complexity: Time complexity for the solution will be O(n) where n is the length of input num string.
Space complexity: O(n) for storing elements into stack.
Above implementations source code can be found at
GitHub link for Java code