Remove k Digits
Monotonic Stack & Queue Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Remove k Digits: How can we remove k digits from a number to form the smallest possible number?, Strings, String Manipulation, Stack, Greedy Algorithm, Time Complexity, Space Complexity, Optimization, greedy algorithm, string manipulation, complexity analysis, stack.
Problem Statement Given a non negative integer num represented as a string, and an integer k, remove k digits from num such that the new number is the smallest possible. Input The input consists of two parts: 1. A string num representing a non negative integer. 2. An integer k, the number of digits to remove. Output Return a string representing the smallest possible integer after removing k digits. The result should not have leading zeros unless it is the number "0" itself. Constraints 1 <= num.length <= 10^5 0 <= k <= num.length num consists of only digits. num does not have any leading zeros except for the zero itself (e.g., "0" is valid, but "012" is not). Sample Test Cases Sample 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to get the new number 1219 which is the smallest. Sample 2: Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the remainder is 200. Note that the output must not contain leading zeros. Sample 3: Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it becomes an empty string, which is treated as 0.