Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/402.html

402. Remove K Digits (Medium)

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.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

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.

Related Topics:
Stack, Greedy

Similar Questions:

Solution 1. Mono Stack

Intuition

We want the answer as lexigraphically smaller as possible, so we should use a mono-increasing stack which will keep tightening towards lexigraphically smaller result.

Algorithm

Use a string ans as a mono-increasing stack.

For each character in s, we push it into ans. And before pushing, we need to pop greater characters in ans first.

For each character we popped, we need to decrement k. And we only keep popping of k > 0.

If after traversing all characters in s, k is still not exhausted, we pop back from s until k == 0.

Lastly, removing leading zeros.

// OJ: https://leetcode.com/problems/remove-k-digits/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string removeKdigits(string s, int k) {
        if (k == s.size()) return "0";
        string ans;
        for (int i = 0, N = s.size(); i < N; ++i) {
            while (k > 0 && ans.size() && s[i] < ans.back()) {
                ans.pop_back();
                --k;
            }
            ans.push_back(s[i]);
        }
        while (k > 0) {
            ans.pop_back();
            --k;
        }
        int i = 0;
        while (i < ans.size() && ans[i] == '0') ++i;
        return i == ans.size() ? "0" : ans.substr(i);
    }
};

Or

// OJ: https://leetcode.com/problems/remove-k-digits/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string removeKdigits(string s, int k) {
        string ans;
        for (int i = 0, N = s.size(); i < N; ++i) {
            while (ans.size() && i - ans.size() < k && s[i] < ans.back()) ans.pop_back(); // We've visited `i` elements and kept `ans.size()` elements, so we've removed `i - ans.size()` elements. If `i - ans.size() < k`, we can continue popping; otherwise, we should stop popping because that will result in excessive popping.
            if (ans.size() < N - k) ans.push_back(s[i]); // We can only keep exactly `N - k` elements in `ans`, so we only push if `ans.size < N - k`.
        }
        auto begin = ans.find_first_not_of('0');
        return begin == string::npos ? "0" : ans.substr(begin);
    }
};

  • class Solution {
    public String removeKdigits(String num, int k) {
        int length = num.length();
        if (k >= length)
            return "0";
        Stack<Integer> stack = new Stack<Integer>();
        int index = 0;
        while (index < length) {
            if (k == 0)
                break;
            int val = num.charAt(index) - '0';
            while (!stack.isEmpty() && val < stack.peek() && k > 0) {
                stack.pop();
                k--;
            }
            if (!stack.isEmpty() || val != 0)
                stack.push(val);
            index++;
        }
        while (k > 0) {
            stack.pop();
            k--;
        }
        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty())
            sb.insert(0, String.valueOf(stack.pop()));
        if (index < length)
            sb.append(num.substring(index));
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

############

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;
    }
}

  • class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack, remain = [], len(num) - k
        for value in num:
            while k and stack and stack[-1] > value:
                k = k - 1
                stack.pop()
            stack.append(value)
        return "".join(stack[:remain]).lstrip('0') or '0'

############

class Solution(object):
  def removeKdigits(self, num, k):
    """
    :type num: str
    :type k: int
    :rtype: str
    """
    stack = []
    for c in num:
      while k > 0 and stack and stack[-1] > c:
        stack.pop()
        k -= 1
      stack.append(c)
    if k > 0:
      stack = stack[:-k]
    return "".join(stack).lstrip("0") or "0"


  • 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"
}

  • function removeKdigits(num: string, k: number): string {
    let nums = [...num];
    while (k > 0) {
        let idx = 0;
        while (idx < nums.length - 1 && nums[idx + 1] >= nums[idx]) {
            idx++;
        }
        nums.splice(idx, 1);
        k--;
    }
    return nums.join('').replace(/^0*/g, '') || '0';
}

All Problems

All Solutions