402. Remove K Digits

Description

Given a non-negative integer num represented as a string, and an integer k, remove k digits from the number so that the resulting number is the smallest possible. The result should not contain leading zeros unless the result is exactly "0".

Intuition

The problem can be thought of as selecting digits in a greedy manner to form the smallest possible number. At each step, we aim to remove digits that make the number larger. For example, we prefer smaller digits earlier in the number as they contribute to a smaller overall value.

Approach

1. Use a stack to build the smallest number possible: - Traverse the digits in the number one by one. - For each digit, if the stack is non-empty, and the top of the stack is greater than the current digit, pop the stack (i.e., remove the larger digit) as long as we have remaining digits (k) to remove. - Add the current digit to the stack.
2. After processing all digits, if we still have digits to remove (k > 0), pop the remaining digits from the stack.
3. Finally, construct the result from the stack, ensuring there are no leading zeros.
4. If the result is an empty string, return "0" as the answer.

Complexity

Time Complexity:

O(n), where n is the length of the input number string. Each digit is pushed and popped from the stack at most once.

Space Complexity:

O(n), for the stack to store the digits.

Code

C++

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector stack;

        for (char d : num) {
            while (!stack.empty() && k > 0 && stack.back() > d) {
                stack.pop_back();
                k--;
            }
            stack.push_back(d);
        }

        while (k > 0) {
            stack.pop_back();
            k--;
        }

        string result = "";
        for (char c : stack) {
            if (!(result.empty() && c == '0')) {
                result.push_back(c);
            }
        }

        return result.empty() ? "0" : result;
    }
};

Python

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []

        for d in num:
            while stack and k > 0 and stack[-1] > d:
                stack.pop()
                k -= 1
            stack.append(d)

        while k > 0:
            stack.pop()
            k -= 1

        # Remove leading zeros
        result = ''.join(stack).lstrip('0')

        return result if result else '0'

Java

class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder stack = new StringBuilder();

        for (char d : num.toCharArray()) {
            while (stack.length() > 0 && k > 0 && stack.charAt(stack.length() - 1) > d) {
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }
            stack.append(d);
        }

        while (k > 0) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }

        while (stack.length() > 0 && stack.charAt(0) == '0') {
            stack.deleteCharAt(0);
        }

        return stack.length() == 0 ? "0" : stack.toString();
    }
}

JavaScript

var removeKdigits = function (num, k) {
    const stack = [];
    for (let d of num) {
        while (stack.length > 0 && k > 0 && stack[stack.length - 1] > d) {
            stack.pop();
            k--;
        }
        stack.push(d);
    }

    while (k > 0) {
        stack.pop();
        k--;
    }

    while (stack.length > 0 && stack[0] == '0') {
        stack.shift()
    }
    return stack.length === 0 ? '0' : stack.join('');
};