402. Remove K Digits

[mah-shamim]

Topics: String, Stack, Greedy, Monotonic Stack

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.

[mah-shamim]

We can use a greedy approach with a stack. The goal is to build the smallest possible number by iteratively removing digits from the given number while maintaining the smallest possible sequence.

Approach:

1. Use a Stack: Traverse through each digit of the number. Push digits onto a stack while ensuring that the digits in the stack form the smallest possible number.
2. Pop from Stack: If the current digit is smaller than the top of the stack, and we still have k digits to remove, pop the stack to remove the larger digits.
3. Handle Remaining Digits: If there are still digits to remove after processing all the digits in num, remove them from the end of the stack.
4. Build the Result: Construct the final number from the digits left in the stack. Ensure to strip any leading zeros.
5. Edge Cases: If the result is an empty string after all removals, return "0".

Let's implement this solution in PHP: 402. Remove K Digits

<?php
/**
 * @param String $num
 * @param Integer $k
 * @return String
 */
function removeKdigits($num, $k) {
    $stack = [];
    $len = strlen($num);

    for ($i = 0; $i < $len; $i++) {
        $digit = $num[$i];
        
        // Remove digits from the stack if the current digit is smaller and we still have digits to remove
        while ($k > 0 && !empty($stack) && end($stack) > $digit) {
            array_pop($stack);
            $k--;
        }
        
        // Push the current digit onto the stack
        $stack[] = $digit;
    }

    // If we still have digits to remove, remove them from the end
    while ($k > 0) {
        array_pop($stack);
        $k--;
    }

    // Build the final result, removing leading zeros
    $result = ltrim(implode('', $stack), '0');

    // Return "0" if the result is empty
    return $result === '' ? '0' : $result;
}

// Example usage:
echo removeKdigits("1432219", 3); // Output: "1219"
echo removeKdigits("10200", 1);   // Output: "200"
echo removeKdigits("10", 2);      // Output: "0"
?>

Explanation:

• Stack-Based Greedy Approach: We maintain a stack to store the digits of the smallest possible number. As we iterate through the digits in num, we compare the current digit with the top of the stack. If the current digit is smaller and we still have digits to remove (k > 0), we pop the stack to remove the larger digit.
• Post-Processing: After processing all digits, if we still need to remove more digits (k > 0), we pop from the stack until k becomes 0.
• Edge Cases: We handle leading zeros by using ltrim to remove them. If the result is an empty string, we return "0".

Time Complexity:

The time complexity of this solution is (O(n)), where n is the length of the input string num. This is because each digit is pushed and popped from the stack at most once.

This solution efficiently handles the constraints and provides the correct output for the given examples.

[kovatz]

Thanks to solve the "Remove K Digits" problem

[mah-shamim]

Thanks