402. Remove K Digits
1. Description
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
2. Note
- The length of num is less than 10002 and will be ≥ k.
- The given num does not contain any leading zero.
3. Example
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.
4. Solutions
My Accepted Solution
n = m_num.size()
Time complexity: O(nk)
Space complexity: O(1)
class Solution
{
public:
// string removeKdigits(string num, int k)
string removeKdigits(string &m_num, int k)
{
if(m_num.size() == k) return string("0");
// 1. try to find and erase '0' to delete more digits, since erase one more digit could significantlly decrease the number
for(int i = 0; i < m_num.size() && k > 0; i++)
{
if(m_num[i] == '0')
{
if(i > k) break; // even we delete leading k digits, we can't reach this '0'
// delete '0' and digits before it
k -= i;
while(i < m_num.size() && m_num[i] == '0') i++;
m_num.erase(0, i);
i = -1; // it will i++ and become 0 at the for loop
if(m_num.empty()) return string("0");
}
}
// 2. try to decrease a digit having high weight
// for example, 14321, if we delete 4, which has weight 1000, then we could let 3 replace 4, so we could decrease 1000 for the whole number
// so we should try to delete the digit with higher weight and let a lower number to replace it
// we add a "0" at the end to simplify the process, since every digit is no less than 0
m_num = m_num + "0";
for(int i = 0; i < m_num.size() && k > 0; )
{
if(m_num[i] > m_num[i + 1])
{
m_num.erase(i, 1);
i = max(0, i - 1);
k--;
}
else
{
i++;
}
}
m_num.erase(m_num.size() - 1); // delete the assist 0
return m_num;
}
};
4.1 Stack
n = m_num.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// string removeKdigits(string num, int k)
string removeKdigits(string &m_num, int k)
{
if(m_num.size() == k) return string("0");
string result;
for(auto digit : m_num)
{
while(k > 0 && !result.empty() && result.back() > digit)
{
result.pop_back(); // try to delete the digit with higher weight
k--;
}
if(result.empty() && digit == '0') continue; // pass leading zero
result.push_back(digit);
}
while(k > 0) // same like the 0 at the end, when the digit is increasing, delete later bigger digits
{
result.pop_back();
k--;
}
return (result.empty() ? string("0") : result);
}
};