Remove K Digits

                                            
class Solution {
public:
    string removeKdigits(string num, int k) {
        string result = "";
        int keep = num.size() - k;
        
        for (char &c : num) {
            while (k && result.size() && result.back() > c) {
                result.pop_back();
                k--;
            }
            result.push_back(c);
        }
        
        result.resize(keep);
        
        while (!result.empty() && result[0] == '0') {
            result.erase(0, 1);
        }
        
        return result.empty() ? "0" : result;
    }
};

                                            
class Solution {
    public String removeKdigits(String num, int k) {
        if (k == num.length()) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for (char c : num.toCharArray()) {
            while (k > 0 && !stack.isEmpty() && stack.peek() > c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }

        while (k > 0) {
            stack.pop();
            k--;
        }

        while (!stack.isEmpty()) {
            sb.insert(0, stack.pop());
        }

        while (sb.length() > 1 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }

        return sb.toString();
    }
}

                                            
class Solution(object):
    def removeKdigits(self, num, k):
        stack = []
        
        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        
        while k > 0:
            stack.pop()
            k -= 1
        
        result = "".join(stack).lstrip("0")
        
        if not result:
            return "0"
        
        return result

                                            
char* removeKdigits(char* num, int k) {
    int len = strlen(num);
    
    if (len == k) {
        char* res = (char*)malloc(2 * sizeof(char));
        res[0] = '0';
        res[1] = '\0';
        return res;
    }
    
    int top = 0;
    char stack[len];
    
    for (int i = 0; i < len; i++) {
        while (k > 0 && top > 0 && stack[top - 1] > num[i]) {
            top--;
            k--;
        }
        stack[top++] = num[i];
    }
    
    while (k > 0) {
        top--;
        k--;
    }
    
    while (top > 0 && stack[0] == '0') {
        for (int i = 0; i < top - 1; i++) {
            stack[i] = stack[i + 1];
        }
        top--;
    }
    
    if (top == 0) {
        char* res = (char*)malloc(2 * sizeof(char));
        res[0] = '0';
        res[1] = '\0';
        return res;
    } else {
        char* res = (char*)malloc((top + 1) * sizeof(char));
        for (int i = 0; i < top; i++) {
            res[i] = stack[i];
        }
        res[top] = '\0';
        return res;
    }
}

                                            
/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function(num, k) {
    const stack = [];
    let count = 0;
    
    for (let i = 0; i < num.length; i++) {
        while (stack.length && num[i] < stack[stack.length - 1] && count < k) {
            stack.pop();
            count++;
        }
        stack.push(num[i]);
    }
    
    while (count < k) {
        stack.pop();
        count++;
    }
    
    while (stack[0] === '0') {
        stack.shift();
    }
    
    return stack.length ? stack.join('') : '0';
};

                                            
function removeKdigits(num: string, k: number): string {
    const stack: string[] = [];
    
    for (let digit of num) {
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }
    
    while (k > 0) {
        stack.pop();
        k--;
    }
    
    // Remove leading zeros
    while (stack.length > 1 && stack[0] === '0') {
        stack.shift();
    }
    
    return stack.join('') || '0';
};

                                            
class Solution {
    /**
     * @param String $num
     */
    function removeKdigits($num, $k) {
        $stack = [];
        
        for ($i = 0; $i < strlen($num); $i++) {
            $digit = $num[$i];
            while ($k > 0 && !empty($stack) && $stack[count($stack) - 1] > $digit) {
                array_pop($stack);
                $k--;
            }
            array_push($stack, $digit);
        }
        
        while ($k > 0) {
            array_pop($stack);
            $k--;
        }
        
        $result = ltrim(implode('', $stack), '0');
        
        return $result === '' ? '0' : $result;
    }
}

                                            
class Solution {
    func removeKdigits(_ num: String, _ k: Int) -> String {
        var k = k
        var stack = [Character]()
        
        for digit in num {
            while k > 0 && !stack.isEmpty && stack.last! > digit {
                stack.removeLast()
                k -= 1
            }
            stack.append(digit)
        }
        
        while k > 0 {
            stack.removeLast()
            k -= 1
        }
        
        // Remove leading zeros
        while !stack.isEmpty && stack.first! == "0" {
            stack.removeFirst()
        }
        
        return stack.isEmpty ? "0" : String(stack)
    }
}

                                            
class Solution {
  String removeKdigits(String num, int k) {
    List<String> stack = [];
    
    for (int i = 0; i < num.length; i++) {
      String digit = num[i];
      
      while (k > 0 && stack.isNotEmpty && int.parse(stack.last) > int.parse(digit)) {
        stack.removeLast();
        k--;
      }
      
      stack.add(digit);
    }
    
    for (int i = 0; i < k; i++) {
      stack.removeLast();
    }
    
    String result = stack.join().replaceAll(RegExp('^0+'), '');
    
    return result.isEmpty ? '0' : result;
  }
}

                                            
func removeKdigits(num string, k int) string {
    stack := []rune{}
    
    for _, digit := range num {
        for k > 0 && len(stack) > 0 && stack[len(stack)-1] > digit {
            stack = stack[:len(stack)-1]
            k--
        }
        
        if len(stack) > 0 || digit != '0' {
            stack = append(stack, digit)
        }
    }
    
    for k > 0 && len(stack) > 0 {
        stack = stack[:len(stack)-1]
        k--
    }
    
    if len(stack) == 0 {
        return "0"
    }
    
    return string(stack)
}

                                            
# @param {String} num
# @param {Integer} k
# @return {String}
def remove_kdigits(num, k)
    stack = []
    
    num.each_char do |digit|
        while k > 0 && !stack.empty? && stack[-1] > digit
            stack.pop
            k -= 1
        end
        stack << digit
    end
    
    stack.pop(k)
    
    result = stack.join("").sub(/^0+/, "")
    
    result.empty? ? "0" : result
end

To solve this coding challenge, we need to identify how to strategically remove

k

digits from the string

num

, representing a non-negative integer, to produce the smallest possible integer. The solution leverages a greedy algorithm to remove digits in a way that minimizes the final number. Let's break down the steps for this solution in detail and provide a suitable pseudocode.

# Explanation

Clarifying the Problem Statement

We start with a string
num

representing a non-negative integer.
We also have an integer
k

which denotes the number of digits we need to remove from
num

.
Our goal is to form the smallest possible integer after removing these
k

digits.
We need to ensure that there are no leading zeros in our final result unless the entire result is just "0".

Approach to Solve the Problem

We will use a stack to implement the greedy strategy for solving this problem. The stack helps in maintaining the digits of the resulting smallest number efficiently.
Traverse each digit of the given string
num

. For each digit, we compare it with the top of the stack (the most recently added digit). If the current digit is smaller than the top of the stack and we still have some digits to remove (
k > 0

), we pop the stack to remove the top digit. This ensures that smaller digits are prioritized and larger digits are removed if they are not the most optimal choice.
Once every digit has been processed, there could still be remaining digits to remove (
k > 0

). In this case, we trim the digits from the end of the stack.
After trimming the necessary digits, we concatenate the stack to form our final result.
Ensure to strip any leading zeros from the result. If the final result is empty, return "0".

# Pseudocode

                                            
# Main function to remove k digits to form the smallest number
function removeKdigits(num: string, k: int) -> string:
# Initialize an empty stack to store digits of the resulting number
stack = []

# Iterate over each digit in the given number string `num`
for digit in num:
# While there are still digits to remove (`k > 0`) and the stack is not empty
# and the last digit in the stack is greater than the current digit
while k > 0 and stack is not empty and stack[-1] > digit:
# Pop the last digit from the stack (remove it) and decrement k
stack.pop()
k -= 1
# Push the current digit onto the stack
stack.append(digit)

# After processing all digits, if k is still greater than 0, remove the last k digits
while k > 0:
stack.pop()
k -= 1

# Join the stack into a string and remove any leading zeros
result = "".join(stack).lstrip("0")

# If the result is empty, return "0"
if result == "":
return "0"

# Return the resulting smallest number
return result

# Step-by-Step Explanation/Detailed Steps in Pseudocode

Create an empty list
stack

to hold the digits of the resulting number.
Traverse each character
digit

in the input string
num

.

Inside the loop, while
k

is greater than 0,
stack

is not empty, and the last element in
stack

is greater than
digit

:

Remove the last element from
stack

(this ensures a smaller number will form).
Decrease
k

by 1 to account for the removed digit.

Append the current
digit

to the
stack

.

Once the entire string
num

has been processed,
k

might still be greater than 0. If so, remove the last
k

digits from the stack by popping
k

times.
Join all elements of
stack

to form a string and remove leading zeroes using
lstrip("0")

.
If the resulting string is empty, return "0".
Otherwise, return the processed string that represents the smallest number possible.