402. Remove K Digits

📝 Problem Details

• Title: 402. Remove K Digits
• **Link:**https://leetcode.com/problems/remove-k-digits/
• Difficulty: Medium
• Tags/Categories: Strings Greedy Stack

input string num representing a non-negative integer input integer k return the smallest possible integer after removing k digits for num

💡 Explanation of Solution

Greedy:
- if the previous digit is larger than the current digit, then keeping it would make the number bigger
- in the event of the above ^ - pop it out
	- greedy removal decision

Stack:
- the stack keeps track of the current best sequence 
- lets you look back at the previous digits in order to make a greedy decision
- enables O(n) efficient removals from the end, simulating backtracking 

Example : nums = "1432219", k = 3

'1'   → stack = ['1']
'4'   → stack = ['1', '4']
'3'   → 4 > 3 → pop '4' → k = 2 → stack = ['1', '3']
'2'   → 3 > 2 → pop '3' → k = 1 → stack = ['1', '2']
'2'   → stack = ['1', '2', '2']
'1'   → 2 > 1 → pop '2' → k = 0 → stack = ['1', '2', '1']
'9'   → stack = ['1', '2', '1', '9']

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    string removeKdigits(string num, int k) {
        string result; // acts as a stack to build the smallest possible number
 
        for (char digit : num) {
            // While the last digit in result is larger than the current digit
            // and we still have digits to remove (k > 0),
            // we pop it to make the number smaller
            while (!result.empty() && result.back() > digit && k > 0) {
                result.pop_back();
                k--;
            }
            // Append the current digit to the result
            result.push_back(digit);
        }
 
        // If we still have digits to remove (e.g. monotonic increasing input), remove from the end
        while (k-- > 0 && !result.empty()) {
            result.pop_back();
        }
 
        // Remove any leading zeros
        int nonZero = 0;
        while (nonZero < result.size() && result[nonZero] == '0') {
            ++nonZero;
        }
 
        result = result.substr(nonZero); // strip leading zeros
 
        // If result is empty (e.g. all digits removed), return "0"
        return result.empty() ? "0" : result;
    }
};