algoadvance

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. The length of num is less than 10002 and since the integer can be very large, it’s given as a string.

You need to return the smallest number possible after removing k digits.

Examples:

  1. Input: num = "1432219", k = 3
    Output: "1219"
  2. Input: num = "10200", k = 1
    Output: "200"
  3. Input: num = "10", k = 2
    Output: "0"

Clarifying Questions

  1. Can the input number have leading zeros?
    • The input number itself will not have leading zeros unless the entire number is “0”.
  2. What should be returned if all digits are removed?
    • If all digits are removed, return “0”.
  3. Are there constraints on the value of k relative to the length of num?
    • Yes, k will always be less than or equal to the length of num.

Strategy

To obtain the smallest possible number after removing k digits, we can use a Greedy algorithm with a Stack. The idea is to simulate the removal of digits while building the result number:

  1. Iterate through the digits of the input number.
  2. For each digit, if it makes the current number larger, remove it (using the stack to keep track of the digits).
  3. After iterating through all digits, if there are still digits to remove (k > 0), remove them from the end of the current number.
  4. Finally, convert the stack back to the number and strip any leading zeros.

Code

Here’s the Python implementation of the above strategy:

def removeKdigits(num: str, k: int) -> str:
    stack = []
    
    for digit in num:
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    
    # If there are still digits to remove
    final_stack = stack[:-k] if k else stack
    
    # Join stack to form the number and remove leading zeros
    result = ''.join(final_stack).lstrip('0')
    
    # Edge case for returning '0' if the result is empty
    return result if result else '0'

# Example usage
print(removeKdigits("1432219", 3))  # Output: "1219"
print(removeKdigits("10200", 1))    # Output: "200"
print(removeKdigits("10", 2))       # Output: "0"

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string num. This is because we process each digit at most once, either pushing it onto or popping it from the stack. The space complexity is also O(n) due to the storage required for the stack.

This solution is efficient and handles edge cases such as numbers with leading zeros effectively.

Try our interview co-pilot at AlgoAdvance.com