Remove K Digits

Problem Statement

In this problem, we are given a string num representing a non-negative integer and an integer k. Our goal is to determine the smallest possible integer that can be formed by removing exactly k digits from num. The result must be returned as a string. This task tests the ability to understand and manipulate number sequences and string data types efficiently, especially considering larger sizes due to the problem's constraints.

Examples

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.

Constraints

• 1 <= k <= num.length <= 105
• num consists of only digits.
• num does not have any leading zeros except for the zero itself.

Approach and Intuition

The challenge here lies in determining which k digits to remove from the string num in order to form the smallest possible number. The direct approach might involve generating all possible numbers after removing k digits and then picking the smallest, but such an approach would not be feasible due to time complexity, especially with the upper constraint limits.

Here's a more intuitive approach to solving this problem:

1. Use a greedy strategy to build the smallest number by removing k digits.
2. Iterate over num and use a stack to keep track of the best numbers to form the smallest integer:
   • For each digit in num, if this digit is smaller than the digit at the top of the stack, pop the stack (i.e., remove that digit from our potential answer), given that you still can remove more digits (k is greater than zero).
   • Push the current digit onto the stack.
   • Decrease k each time a digit is removed.
3. By the end of this process, the stack contains the digits of the answer in order but might be larger than required if k was not exhausted. Trim the remaining digits from the end if any.
4. Convert the stack back to a string and ensure leading zeros are removed (except for the zero itself if it's the final result).

Key Considerations:

• If k equals the length of num, the result should be "0" since all digits will be removed.
• Care must be taken to handle removals that result in a number with leading zeros. Post-processing steps should ensure these zeros are stripped, unless the final number is zero.

Example Walkthroughs:

Example 1: ("1432219", k = 3)

• Iteratively compare and choose to skip '4', '3', and the second '2' to eventually form '1219'.

Example 2: ("10200", k = 1)

• Removing the leading '1' and handling leading zeros post-removal gives '200'.

Example 3: ("10", k = 2)

• Remove all digits leading to '0' as all digits are removed.

This greedy minimization strategy using a stack provides an optimal solution both in terms of time and space complexity compared to brute-force methods.

Solutions

class Solution {
  public String stripKdigits(String number, int k) {
    LinkedList<Character> stack = new LinkedList<Character>();
        
    for(char digit : number.toCharArray()) {
      while(stack.size() > 0 && k > 0 && stack.peekLast() > digit) {
        stack.removeLast();
        k -= 1;
      }
      stack.addLast(digit);
    }
        
    for(int i = 0; i < k; ++i) {
      stack.removeLast();
    }
        
    StringBuilder result = new StringBuilder();
    boolean skipLeadingZeros = true;
    for(char digit: stack) {
      if(skipLeadingZeros && digit == '0') continue;
      skipLeadingZeros = false;
      result.append(digit);
    }
        
    if (result.length() == 0) return "0";
    return result.toString();
  }
}