In this Leetcode Remove K Digits problem solution we have given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Leetcode Remove K Digits problem solution


Problem solution in Python.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        if (k == len(num)):
            return "0"
        
        stack = []
        stack.append(num[0])
        i = 1
        while i < len(num) and k > 0:
            if len(stack)>0 and int(num[i]) < int(stack[-1]):                    
                stack.pop()    
                k -= 1
            else:
                stack.append(num[i])
                i += 1
        
        finalnum = "".join(stack)  
        finalnum += num[i:]
        
        if k>0:
            finalnum = finalnum[:-k]
        
        return self.remzeros(finalnum)
    
    def remzeros(self, s):
        if (len(s)==0):
            return '0'
        while (s[0]=='0'):
            s = s[1:]
            if (len(s)==0):
                return '0'
        
        return s



Problem solution in Java.

public String removeKdigits(String num, int k) {
        if (num.length() == 0 || num.length() == k) return "0";
        if (k == 0) return num;
        
        int n = num.length();
        for (int i = 0; i < n-1; i++) {
            if (num.charAt(i) > num.charAt(i+1)) {
                String tmp = num.substring(0, i) + num.substring(i+1);
                tmp = trim(tmp);
                return removeKdigits(tmp, k-1);
            }
        }
        return num.substring(0, n-k);
    }
    
    String trim(String s) {
        int i = 0;
        while (i < s.length() && s.charAt(i) == '0') {
            i++;
        }
        return s.substring(i);
    }


Problem solution in C++.

string removeKdigits(string num, int k) {
        if(k <= 0) return num; 
        if(k >= num.size()) return "0";
        while(k-- > 0){
            int i = 0;
            for(; i <num.size() - 1; ++i)
                if(num[i + 1] < num[i]) break; 
            num.erase(i, 1);
            i = 0;
            for(; i < num.size(); ++i)
                if(num[i] != '0') break;
            if(i == num.size()) return "0";
            if(i > 0) num.erase(0, i);
        }
        return num; 
    }


Problem solution in C.

#define STACK_SZ 100000

char * removeKdigits(char * num, int k)
{
    int n = strlen(num);
    char stack[STACK_SZ];
    int head = -1;
    
    for (int i = 0; i < n; i++) {
        while (head != -1 && k && stack[head] > num[i]) {
            --head;
            --k;
        }
        if (head != -1 || num[i] != '0')
            stack[++head] = num[i];
    }
    
    while (k-- && head != -1)
        --head;
	
    if (head == -1)
        return "0";

    while (head != -1)
        num[--n] = stack[head--];
    
    return num + n;
}