Skip to content

402. Remove K Digits

DifficultyMedium

Description

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

 

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.

Solutions

Solution 1: Greedy Algorithm

Thinking

After deleting \(k\) digits we want the smallest remaining number. Equal-length integers are compared from the first differing digit, so larger digits on the left should be removed first.

A non-decreasing stack from left to right pops the top whenever the current digit is smaller, spending one deletion. Then keep the leftover length and strip leading zeros.

The scan has to go left to right: a smaller digit can occupy a higher place only after a larger left digit is gone.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stk = []
        remain = len(num) - k
        for c in num:
            while k and stk and stk[-1] > c:
                stk.pop()
                k -= 1
            stk.append(c)
        return ''.join(stk[:remain]).lstrip('0') or '0'

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder stk = new StringBuilder();
        for (char c : num.toCharArray()) {
            while (k > 0 && stk.length() > 0 && stk.charAt(stk.length() - 1) > c) {
                stk.deleteCharAt(stk.length() - 1);
                --k;
            }
            stk.append(c);
        }
        for (; k > 0; --k) {
            stk.deleteCharAt(stk.length() - 1);
        }
        int i = 0;
        for (; i < stk.length() && stk.charAt(i) == '0'; ++i) {
        }
        String ans = stk.substring(i);
        return "".equals(ans) ? "0" : ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string removeKdigits(string num, int k) {
        string stk;
        for (char& c : num) {
            while (k && stk.size() && stk.back() > c) {
                stk.pop_back();
                --k;
            }
            stk += c;
        }
        while (k--) {
            stk.pop_back();
        }
        int i = 0;
        for (; i < stk.size() && stk[i] == '0'; ++i) {
        }
        string ans = stk.substr(i);
        return ans == "" ? "0" : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func removeKdigits(num string, k int) string {
    stk, remain := make([]byte, 0), len(num)-k
    for i := 0; i < len(num); i++ {
        n := len(stk)
        for k > 0 && n > 0 && stk[n-1] > num[i] {
            stk = stk[:n-1]
            n, k = n-1, k-1
        }
        stk = append(stk, num[i])
    }

    for i := 0; i < len(stk) && i < remain; i++ {
        if stk[i] != '0' {
            return string(stk[i:remain])
        }
    }
    return "0"
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function removeKdigits(num: string, k: number): string {
    const stk: string[] = [];
    for (const c of num) {
        while (k && stk.length > 0 && stk[stk.length - 1] > c) {
            stk.pop();
            k--;
        }
        stk.push(c);
    }
    while (k--) {
        stk.pop();
    }
    return stk.join('').replace(/^0*/g, '') || '0';
}

Comments