Given string num representing a non-negative integer `num`

, and an integer `k`

, return *the smallest possible integer after removing* `k`

*digits from* `num`

.

**Example 1:**

Input:num = "1432219", k = 3Output:"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 = 1Output:"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 = 2Output:"0"Explanation:Remove all the digits from the number and it is left with nothing which is 0.

**Constraints:**

`1 <= k <= num.length <= 10`

^{5}`num`

consists of only digits.`num`

does not have any leading zeros except for the zero itself.

The core challenge of this problem is to remove `k`

digits from the given number `num`

such that the resulting number is the smallest possible. This problem is significant in scenarios where minimizing numerical values is crucial, such as in financial calculations or optimization problems.

Potential pitfalls include removing digits in a way that does not lead to the smallest possible number or ending up with leading zeros in the result.

To solve this problem, we need to think about how to remove digits in a way that minimizes the resulting number. A naive solution would involve generating all possible combinations of the number after removing `k`

digits and then selecting the smallest one. However, this approach is computationally expensive and impractical for large inputs.

Instead, we can use a more optimized approach using a stack data structure. The idea is to iterate through the digits of the number and use the stack to keep track of the digits of the resulting smallest number. We remove digits from the stack if the current digit is smaller than the top of the stack and we still have digits left to remove.

Here is a step-by-step breakdown of the algorithm:

- Initialize an empty stack to keep track of the digits of the resulting number.
- Iterate through each digit of the input number.
- While the stack is not empty, the current digit is smaller than the top of the stack, and we still have digits left to remove, pop the top of the stack.
- Push the current digit onto the stack.
- If there are still digits left to remove after processing all digits, remove them from the end of the stack.
- Construct the resulting number from the stack and remove any leading zeros.
- If the resulting number is empty, return "0".

```
import java.util.*;
public class RemoveKDigits {
public String removeKdigits(String num, int k) {
// Edge case: if k is equal to the length of num, return "0"
if (k == num.length()) {
return "0";
}
// Initialize a stack to keep track of the digits
Deque<Character> stack = new ArrayDeque<>();
// Iterate through each digit in the number
for (char digit : num.toCharArray()) {
// While the stack is not empty, the current digit is smaller than the top of the stack,
// and we still have digits left to remove, pop the top of the stack
while (!stack.isEmpty() && k > 0 && stack.peekLast() > digit) {
stack.pollLast();
k--;
}
// Push the current digit onto the stack
stack.offerLast(digit);
}
// If there are still digits left to remove, remove them from the end of the stack
for (int i = 0; i < k; i++) {
stack.pollLast();
}
// Construct the resulting number from the stack
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
result.append(stack.pollFirst());
}
// Remove leading zeros
while (result.length() > 1 && result.charAt(0) == '0') {
result.deleteCharAt(0);
}
// If the resulting number is empty, return "0"
return result.length() == 0 ? "0" : result.toString();
}
public static void main(String[] args) {
RemoveKDigits solution = new RemoveKDigits();
System.out.println(solution.removeKdigits("1432219", 3)); // Output: "1219"
System.out.println(solution.removeKdigits("10200", 1)); // Output: "200"
System.out.println(solution.removeKdigits("10", 2)); // Output: "0"
}
}
```

The time complexity of this approach is `O(n)`

, where `n`

is the length of the input number. This is because each digit is pushed and popped from the stack at most once. The space complexity is also `O(n)`

due to the stack used to store the digits.

Potential edge cases include:

- When
`k`

is equal to the length of the number, the result should be "0". - When the resulting number has leading zeros, they should be removed.
- When the input number is already the smallest possible, no digits should be removed unnecessarily.

Examples of edge cases and their expected outputs:

Input: num = "10", k = 2 Output: "0" Input: num = "10200", k = 1 Output: "200"

To test the solution comprehensively, consider a variety of test cases, including:

- Simple cases with small numbers.
- Cases with leading zeros in the input number.
- Cases where
`k`

is equal to the length of the number. - Large input cases to test the efficiency of the algorithm.

Using a testing framework like JUnit can help automate and manage these tests effectively.

When approaching such problems, consider the following tips:

- Break down the problem into smaller, manageable parts.
- Think about edge cases and how to handle them.
- Use data structures like stacks or queues to simplify the solution.
- Practice solving similar problems to improve problem-solving skills.

In this blog post, we discussed how to solve the problem of removing `k`

digits from a number to get the smallest possible result. We explored a stack-based approach that is both efficient and easy to understand. By practicing such problems, you can improve your problem-solving skills and become more proficient in algorithm design.

For further reading and practice, consider the following resources: