Stack: April POTD

Question: Remove K Digits -(Medium)

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

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.        

Intuition:

Apporach:

1. Traverse all characters of the String.
2. Push char into stack , and keep checking if the top of stack is greater than current char , then remove top from stack and decrement k.
3. Even after processing,if k is not 0 then remove elements from stack till k==0.
4. Create a new string by popping elements from stack, starting from top and reverse of this newly string will be smallest number formed.
5. In case , new string is starting from 0 , then remove that 0 from the newly formed string.

Code:

Time Complexity : O(n)

Space Complexity: O(n) ,as we use stack to store characters.

Leetcode : https://leetcode.com/problems/remove-k-digits/solutions/5009795/best-solution-96-09-easy-approach-stack/