Approach 1: Naive approach (TLE)
We want to get the lowest number possible by removing “k” digits. Whenever we find a number Y to the right of a number X such that Y < X, we would benefit from deleting X as Y would then occupy it’s location resulting in a smaller number. Consider the number “213”. Here, 1 is to the adjacent right of 2 and it is smaller than 2. If we delete 2, we get a smaller number “13” (if we had deleted 1 instead, we would have gotten “23”. Clearly, 13 is less than 23).
We can simply repeat this procedure k times to get our answer. Note that if we get a number like “12345” or “1123” where no adjacent right digit is greater than the previous digit, we would always benefit from deleting the largest number.
string removeKdigits(string num, int k) {
while (k > 0) {
int n = num.size();
int i = 0;
while (i+1<n && num[i]<=num[i+1]) i++;
num.erase(i, 1);
k--;
}
// trim leading zeros
int s = 0;
while (s<(int)num.size()-1 && num[s]=='0') s++;
num.erase(0, s);
return num=="" ? "0" : num;
}
Time complexity: O(n*k) where n is the size of num
Note that this approach will give TLE.
Approach 2: Greedy
The idea of this approach remains same. We will instead use a stack to make the algorithm linear in time. Algorithm:
- Go through the number from left to right inserting the digits into a stack. The stack always maintains a non-decreasing order.
- Whenever we encounter a digit, pop the digits from stack which are greater than that digit (note that this way stack always maintains non-decreasing order). This is because a number on the left is larger than the current number so we should remove such numbers. Also, do not forget to decrement k as we pop from the stack.
- After iterating the whole string, we have to deal with edge cases like “1111” or “1234”. These arise when the stack still has elements and k is still not 0. Since the stack maintains non-decreasing order, we just have to pop some elements from the stack (as largest element will be on top of stack).
- Surprisingly, there is still one annoying edge case remaining. The resulting string may have leading zeros which we have to remove before returning the string.
The below code is a bit long but the idea is not complex.
class Solution {
public:
string removeKdigits(string num, int k) {
if (k>=num.length())
return "0";
stack<char> st;
for (char c : num) {
// k keeps track of how many characters we can remove
// if the previous character in stk is larger than the current one
// then removing it will get a smaller number
// but we can only do so when k is larger than 0
while (k>0 && !st.empty() && st.top()>c) {
st.pop();
k--;
}
st.push(c);
}
// edge cases like "1111", "12345"
while (k-->0) st.pop();
string res="";
while (!st.empty()) {
res+=st.top();
st.pop();
}
reverse(res.begin(), res.end());
// remove leading zeros if any (coonsider case num="100", k=1)
auto idx = res.length()-1;
for (int i=0; i<res.length(); i++) {
if (res[i]=='0') continue;
idx=i;
break;
}
res = res.substr(idx);
return res;
}
};
Time complexity: O(n)
The code above can be made shorter. Instead of a stack, we can use the answer string itself. Strings in C++ behave just like a vector of characters so they have the pop_back function which we can leverage to simulate stack behavior.
string removeKdigits(string num, int k) {
string ans = ""; // treat ans as a stack in below for loop
for (char c : num) {
while (ans.length() && ans.back() > c && k) {
ans.pop_back(); // make sure digits in ans are in ascending order
k--; // remove one char
}
if (ans.length() || c != '0') { ans.push_back(c); } // can't have leading '0'
}
while (ans.length() && k--) { ans.pop_back(); } // make sure remove k digits in total
return ans.empty() ? "0" : ans;
}