19. Remove K Digits(imp)

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.

Solution: (Stack)

Approach: Removing the peak element from starting

class Solution
{
public:
    string removeKdigits(string num, int k)
    {

        // if remove all digits
        if (num.length() == k)
        {
            return "0";
        }

        stack<char> s;

        for (int i = 0; i < num.length(); i++)
        {

            while (!s.empty() && s.top() > num[i] && k > 0)
            {
                s.pop();
                k--;
            }

            s.push(num[i]);
        }

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

        string res = "";

        while (!s.empty())
        {
            res = s.top() + res;
            s.pop();
        }

        int i = 0;
        // Removing trailing zero
        while (res[i] == '0')
        {
            i++;
        }

        res = res.substr(i, res.length() - i);

        // If string becomes empty
        if (res == "")
        {
            return "0";
        }

        return res;
    }
};

Time Complexity: O(n)