✅ C++ || Easy To Understand || Stack || Short & Simple
402. Remove K Digits\nKNOCKCAT\n\n1. Easy C++\n2. Line by Line Explanation with Comments.\n3. Detailed Explanation \u2705\n4. Handwritten snap of an TestCase at
# 402. Remove K Digits\n**KNOCKCAT**\n```\n1. Easy C++\n2. Line by Line Explanation with Comments.\n3. Detailed Explanation \u2705\n4. Handwritten snap of an TestCase at the end of code given.\n5. Please Upvote if it helps\u2B06\uFE0F\n6. Link to my Github Profile contains a repository of Leetcode with all my Solutions. \u2B07\uFE0F\n```\n**My LeetCode Github Repository**\n[LeetCode](https://github.com/knockcat/Leetcode)\n\n**EXPLANATION**\n```\n1. Deleting k digits means keeping n - k digits, where n is the total number of digits.\n\n2. Use a stack that you keep sorted ascendingly. You remove elements from it as long as you can still make it to n - k digits,\nand your current element is smaller than the top of the stack:\n\npush(2) => 2\npush(4) because 2 < 4 => 24\npush(6) because 4 < 6 => 246\npop() because 3 < 6 and we can still end up with 2 digits => 24\npop() for the same reason => 2\npush(3) => 23\npush(5) => 235\nThen just take the first k digits => 23. Or you can make sure never to push more than k digits, and then the final stack is your solution.\n\n3. Note that you cannot pop elements if that means you will not be able to build a solution of k digits.\nFor this, you need to check the current number of elements in the stack and the number of digits to the right of your current position on the input number.\n```\n\n**Some More Points**\n\n```\n1. Approach is simple. We need a number which is minimum, thus we need to remove the most significant digits first.\nFor eg. if we have a number having digits 1-4 then 1234 would be the minimum and not 2314 or anything else.\nSo in case of 2314, we remove 3 first, and then we go for 2 (Because they are more significant than 4). Observing this simple idea,\nwe need to remove any digit which is greater than its following digit. Thats why we deleted 3 as it,\nwas greater than 1 and similiarly 2 as it was also greater than 1.\n\n2. In order to accomplish this, we use stack Data Structure where we pop the top if it is greater than current digit.\n\n3. The conditions mentioned in while loop are important to avoid any Runtime Error. For eg. ["10001" 2] the answer is "0" but if we don\'t\nmention the condition !s.empty(), then the while loop will run on empty stack and try to pop the top which doesn\'t exist thus throwing RE.\n\n```\n**Time Complexity :- O(N)** *// as we only traversing the string for once*\n**Space complexity:- O(N)** *// as we will store maximum of n digits in our string*\n\n**CODE WITH EXPLANATION**\n```\n\t\t\t\t\t\t\t\t// \uD83D\uDE09\uD83D\uDE09\uD83D\uDE09\uD83D\uDE09Please upvote if it helps \uD83D\uDE09\uD83D\uDE09\uD83D\uDE09\uD83D\uDE09\nclass Solution {\npublic:\n    string removeKdigits(string num, int k) {\n        // number of operation greater than length we return an empty string\n        if(num.length() <= k)   \n            return "0";\n        \n        // k is 0 , no need of removing /  preforming any operation\n        if(k == 0)\n            return num;\n        \n        string res = "";// result string\n        stack <char> s; // char stack\n        \n        s.push(num[0]); // pushing first character into stack\n        \n        for(int i = 1; i<num.length(); ++i)\n        {\n            while(k > 0 && !s.empty() && num[i] < s.top())\n            {\n                // if k greater than 0 and our stack is not empty and the upcoming digit,\n                // is less than the current top than we will pop the stack top\n                --k;\n                s.pop();\n            }\n            \n            s.push(num[i]);\n            \n            // popping preceding zeroes\n            if(s.size() == 1 && num[i] == \'0\')\n                s.pop();\n        }\n        \n        while(k && !s.empty())\n        {\n            // for cases like "456" where every num[i] > num.top()\n            --k;\n            s.pop();\n        }\n        \n        while(!s.empty())\n        {\n            res.push_back(s.top()); // pushing stack top to string\n            s.pop(); // pop the top element\n        }\n        \n        reverse(res.begin(),res.end()); // reverse the string \n        \n        if(res.length() == 0)\n            return "0";\n        \n        return res;\n        \n        \n    }\n};\n```\n\n\n**Dry Run For a Test Case Ask in Comments**\n\n\n![image](https://assets.leetcode.com/users/images/06985b3b-6b5d-4696-b164-4c0e6eb22df5_1645173205.4722228.jpeg)\n
['Stack', 'C']