402. Remove K Digits

Problem 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 <= 10⁵
• num consists of only digits.
• num does not have any leading zeros except for the zero itself.

Python Solution

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        
        # Build monotonic increasing stack
        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        
        # If k > 0, remove remaining digits from end
        while k > 0:
            stack.pop()
            k -= 1
        
        # Build result string
        result = ''.join(stack).lstrip('0')
        
        return result if result else '0'

Java Solution

class Solution {
    public String removeKdigits(String num, int k) {
        Stack stack = new Stack<>();
        
        // Build monotonic increasing stack
        for (char digit : num.toCharArray()) {
            while (k > 0 && !stack.isEmpty() && stack.peek() > digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }
        
        // If k > 0, remove remaining digits from end
        while (k > 0) {
            stack.pop();
            k--;
        }
        
        // Build result string
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.insert(0, stack.pop());
        }
        
        // Remove leading zeros
        while (result.length() > 0 && result.charAt(0) == '0') {
            result.deleteCharAt(0);
        }
        
        return result.length() == 0 ? "0" : result.toString();
    }
}

C++ Solution

class Solution {
public:
    string removeKdigits(string num, int k) {
        string stack;
        
        // Build monotonic increasing stack
        for (char digit : num) {
            while (k > 0 && !stack.empty() && stack.back() > digit) {
                stack.pop_back();
                k--;
            }
            stack.push_back(digit);
        }
        
        // If k > 0, remove remaining digits from end
        while (k > 0) {
            stack.pop_back();
            k--;
        }
        
        // Remove leading zeros
        int start = 0;
        while (start < stack.length() && stack[start] == '0') {
            start++;
        }
        
        string result = stack.substr(start);
        return result.empty() ? "0" : result;
    }
};

JavaScript Solution

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function(num, k) {
    const stack = [];
    
    // Build monotonic increasing stack
    for (const digit of num) {
        while (k > 0 && stack.length && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }
    
    // If k > 0, remove remaining digits from end
    while (k > 0) {
        stack.pop();
        k--;
    }
    
    // Build result string and remove leading zeros
    const result = stack.join('').replace(/^0+/, '');
    
    return result || '0';
};

C# Solution

public class Solution {
    public string RemoveKdigits(string num, int k) {
        var stack = new Stack();
        
        // Build monotonic increasing stack
        foreach (char digit in num) {
            while (k > 0 && stack.Count > 0 && stack.Peek() > digit) {
                stack.Pop();
                k--;
            }
            stack.Push(digit);
        }
        
        // If k > 0, remove remaining digits from end
        while (k > 0) {
            stack.Pop();
            k--;
        }
        
        // Build result string
        var result = new string(stack.Reverse().ToArray());
        
        // Remove leading zeros
        result = result.TrimStart('0');
        
        return string.IsNullOrEmpty(result) ? "0" : result;
    }
}