Problem statement

Given a string num representing a non-negative integer and an integer k, remove exactly k digits so that the remaining number is the smallest possible, and return it as a string (no leading zeros; return "0" if everything is removed).

Example 1

Input: num = "1432219", k = 3
Output: "1219"

Example 2

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the 1; leading zeros are stripped.

Example 3

Input: num = "10", k = 2
Output: "0"

Constraints

• 1 <= k <= num.length <= 20
• num has only digits; no leading zeros except "0" itself.

Hints for Remove K Digits

1. Hint 1

   Greedy with a stack: pop bigger digits from the top while you still may remove.

2. Hint 2

   If removals remain at the end, trim from the right; then strip leading zeros.

How to solve Remove K Digits

The result always has exactly len(num) - k digits, so length is fixed and only the digits themselves matter. For numbers of equal length, the leftmost digit dominates: making an earlier position smaller beats any improvement further right. So whenever a digit is followed by a smaller one, deleting it strictly shrinks the number — and that is a decision you can make greedily, left to right.

Approach

1. Keep a stack of the digits kept so far and a budget k of deletions.
2. For each digit ch: while budget remains and the stack top is greater than ch, pop it and spend one deletion.
3. Push ch.
4. If budget remains after the scan, the kept digits are non-decreasing — remove the last k from the right.
5. Strip leading zeros, and return "0" if nothing is left.

Why it works

A digit with a smaller digit after it is bad in its position: deleting it promotes something smaller into a more significant place, which always lowers the value. Deleting it as early as possible is safe because the digits before it are already no greater than it. Once the kept digits are non-decreasing, no deletion can improve a leading position, so the cheapest remaining deletions are the least significant ones at the right end.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Leftover deletions must come off the right. Taking them from the left would drop the most significant digits, which is the opposite of what you want.
• Strip leading zeros only at the end — "10200" with k = 1 becomes "0200" and then "200".
• Removing everything must return the string "0", not an empty string.
• The pop test is strictly >. Popping on equal digits wastes deletions without lowering the value.

Reference solution

Python

def removeKdigits(num: str, k: int) -> str:
    st = []
    for ch in num:
        while k > 0 and st and st[-1] > ch:
            st.pop()
            k -= 1
        st.append(ch)
    while k > 0:
        st.pop()
        k -= 1
    out = "".join(st).lstrip("0")
    return out if out else "0"

Java

public static String removeKdigits(String num, int k) {
    StringBuilder st = new StringBuilder();
    int rem = k;
    for (char ch : num.toCharArray()) {
        while (rem > 0 && st.length() > 0 && st.charAt(st.length() - 1) > ch) {
            st.deleteCharAt(st.length() - 1);
            rem--;
        }
        st.append(ch);
    }
    while (rem > 0 && st.length() > 0) {
        st.deleteCharAt(st.length() - 1);
        rem--;
    }
    int i = 0;
    while (i < st.length() && st.charAt(i) == '0') i++;
    String out = st.substring(i);
    return out.isEmpty() ? "0" : out;
}

C++

string removeKdigits(string num, int k) {
    string st;
    int rem = k;
    for (char ch : num) {
        while (rem > 0 && !st.empty() && st.back() > ch) {
            st.pop_back();
            rem--;
        }
        st.push_back(ch);
    }
    while (rem > 0 && !st.empty()) {
        st.pop_back();
        rem--;
    }
    size_t i = 0;
    while (i < st.size() && st[i] == '0') i++;
    string out = st.substr(i);
    return out.empty() ? "0" : out;
}

JavaScript

var removeKdigits = function(num, k) {
    const st = [];
    for (const ch of num) {
        while (k > 0 && st.length > 0 && st[st.length - 1] > ch) {
            st.pop();
            k--;
        }
        st.push(ch);
    }
    while (k > 0) { st.pop(); k--; }
    const out = st.join("").replace(/^0+/, "");
    return out === "" ? "0" : out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium