Practice/Amazon/Leetcode 402. Remove K Digits

Leetcode 402. Remove K Digits

CodingMust

Problem

You are given a string representing a non-negative integer num and an integer k. Your task is to remove exactly k digits from the number so that the resulting number is as small as possible. The relative order of the remaining digits must be preserved.

Return the smallest possible number as a string. If all digits are removed, return "0".

Requirements

1. Remove exactly k digits from the input string
2. Maintain the relative order of remaining digits
3. Remove any leading zeros from the result
4. If the result is empty or all zeros, return "0"
5. The input string contains only digit characters

Constraints

• 1 ≤ k ≤ num.length ≤ 10⁵
• num consists of only digits
• num does not have any leading zeros except for the zero itself
• Expected time complexity: O(n) where n is the length of num
• Expected space complexity: O(n)

Examples

Example 1:

Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 (first occurrence) 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 result is 0200. After removing leading zeros, we get 200.

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.

Example 4:

Input: num = "9", k = 1 Output: "0" Explanation: Removing the only digit leaves us with an empty result, which is represented as "0".