Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

Remove K Digits

Medium · Stack & Queue · Asked at Amazon, Google, Microsoft, Adobe, Snapchat

Remove exactly k digits from the number num so that the remaining number is as small as possible. Print it without leading zeros; print 0 if nothing (or only zeros) remains.

Input

First line: num (digits, no leading zeros unless it is 0). Second line: k.

Output

The smallest possible number.

Constraints

Greedy with a stack: while the previous digit is larger than the current one and removals remain, pop it. Remove any leftover k from the end.

Example 1

Input

1432219
3

Output

1219

Example 2

Input

10200
1

Output

200

Hints

  1. A smaller digit earlier in the number matters more than anything later.
  2. Scan left to right with a stack: while removals remain and the previous digit is larger than the current one, delete the previous digit.

Approach

Greedy with a monotonic stack: for each digit d, pop while k > 0 and the top is greater than d (removing a larger digit before a smaller one always makes the number smaller), then push d. If removals remain, the stack is non-decreasing, so remove from the end. Strip leading zeros; if nothing is left, the answer is "0".

Complexity: O(n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string num;
    int k;
    cin >> num >> k;
    string st;
    for (char d : num) {
        while (k > 0 && !st.empty() && st.back() > d) st.pop_back(), k--;
        st.push_back(d);
    }
    while (k-- > 0) st.pop_back();
    size_t i = 0;
    while (i < st.size() && st[i] == '0') i++;
    string res = st.substr(i);
    cout << (res.empty() ? "0" : res) << "\n";
    return 0;
}

Python solution

import sys

data = sys.stdin.read().split()
num, k = data[0], int(data[1])
st = []
for d in num:
    while k and st and st[-1] > d:
        st.pop()
        k -= 1
    st.append(d)
if k:
    st = st[:-k]
print("".join(st).lstrip("0") or "0")

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String num = sc.next();
        int k = sc.nextInt();
        StringBuilder st = new StringBuilder();
        for (char d : num.toCharArray()) {
            while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > d) {
                st.deleteCharAt(st.length() - 1);
                k--;
            }
            st.append(d);
        }
        st.setLength(st.length() - k);
        int i = 0;
        while (i < st.length() && st.charAt(i) == '0') i++;
        String res = st.substring(i);
        System.out.println(res.isEmpty() ? "0" : res);
    }
}

Solve Remove K Digits online · All practice problems