# A greedy method using stack, O(n) time and O(n) space

• ``````public class Solution {
public String removeKdigits(String num, int k) {
int digits = num.length() - k;
char[] stk = new char[num.length()];
int top = 0;
// 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
for (int i = 0; i < num.length(); ++i) {
char c = num.charAt(i);
while (top > 0 && stk[top-1] > c && k > 0) {
top -= 1;
k -= 1;
}
stk[top++] = c;
}
// find the index of first non-zero digit
int idx = 0;
while (idx < digits && stk[idx] == '0') idx++;
return idx == digits? "0": new String(stk, idx, digits - idx);
}
}
``````

• How could you deal with this case ('553', 2) or ('123', 2')?

• @JoeX.TJUF

The variable `digits` ensures the extra ending values would not be included in the final result.

Consider `"123"`, `1`, then `digits == 2`, so that in the end `stk == ['1', '2', '3']`, but the result is the first `digits` values in the `stk`, i.e. `"12"`, instead of `"123"`.

• My solution beats 100%, the main idea is same with others, an optimized part is when k == 0, just copy the left part to newContent and avoid other operation.

``````    public String removeKdigits(String num, int k) {
// simple case pass
if (k == 0) {
return num;
}
int len = num.length();
if (k == len) {
return "0";
}

char[] content = num.toCharArray();
// newContent store the result
char[] newContent = new char[len];

newContent[0] = content[0];
// newIndex points to the next value to be filled in(which means newIndex - 1 is the last value)
int newIndex = 1;
for (int i = 1; i <= len - 1; i++) {
char ch = content[i];
// replace the old value that smaller than ch
while (k > 0 && newIndex >= 1 && ch < newContent[newIndex - 1]) {
newIndex--;
k--;
}
// place ch
newContent[newIndex] = ch;
newIndex++;
// if k is 0, copy the rest to the newContent, the size of rest is (len - 1 - i + 1)
if (k == 0) {
i++;
System.arraycopy(content, i, newContent, newIndex, len - i);
newIndex += (len - i);
break;
}

}
int startIndex = 0;
while (newContent[startIndex] == '0') {
startIndex++;
}
if (newIndex - startIndex - k == 0) {
return "0";
}
return new String(newContent, startIndex, newIndex - startIndex - k);
}
``````

• @JoeX.TJUF the case ("553",2) would give stk=['3','5'], result ="3". The case("123",2) would give stk['1','2','3'], result="1".

The whole idea of this method is to make small number move forward by at most k digits and output a number of length num.length-k.

So ("553",2) would make 3 move 2 digits forward, ending to ['3','5'].
("123",2) would not change, ending to ['1','2','3'].
Then select the small number from the beginning of num.length-k.

• very nice, same idea here in C#

``````    public string RemoveKdigits(string num, int k)
{
int len = num.Length;
Stack<int> stack = new Stack<int>();

for (int i = 0; i < len; i++)
{
while (k > 0 && stack.Count > 0 && num[stack.Peek()] > num[i])
{
stack.Pop();
k--;
}
stack.Push(i);
}

StringBuilder sb = new StringBuilder();
while (stack.Count > 0)
{
sb.Append(num[stack.Pop()]);
if (k-- > 0) sb.Length--;
}

StringBuilder output = new StringBuilder();
for (int i = sb.Length - 1; i >= 0; i--)
{
if (output.Length > 0 || sb[i] != '0') output.Append(sb[i]);
}

return output.Length > 0 ? output.ToString() : "0";
}
``````

• from left to right of the string, put each of char into a new stringbuilder instance.
when `k > 0`, check these chars in the new stringbuilder result from right to left, which one is smaller, keep smaller one.

``````Input: num = "1432219", k = 3

For example, now in stringbuilder is 14. We check '3', 3 is smaller than 4, remove 4, append 3.
now stringbuilder is 13, we check '2', 2 is smaller than 3, remove 3, append 2.
now stringbuilder is 12, we check '2', 2 is equal to 2, append 2.
now stringbuilder is 122, we check `1`, 1 is smaller than 2, remove 2, append 1.
now stringbuilder is 121, now k is 0, we append 9.

Output: "1219"
``````
``````  public String removeKdigits(String num, int k) {
char[] sc = num.toCharArray();
if(k >= sc.length) return "0";
StringBuilder sb = new StringBuilder();
for(char c: sc){
while(sb.length() > 0 && sb.charAt(sb.length() - 1) > c && k > 0){
sb.deleteCharAt(sb.length() - 1);
k--;
}
sb.append(c);
}

// handle case like "0200"
while(sb.length() > 1 && sb.charAt(0) == '0'){
sb.deleteCharAt(0);
}

//handle case like "112", k = 1
for(int i=0; i < k; i++){
sb.deleteCharAt(sb.length() - 1);
}
return sb.toString();
}
````````

• num = "99991"
k = 4

it's wrong~~
if we have a
top--;
we need to check
top-1 with top-2

• sorry you are right

• ``````public String removeKdigits(String num, int k) {
StringBuilder res = new StringBuilder();
for (int i=0; i<num.length(); i++) {
while (res.length()>0 && res.charAt(res.length()-1)>num.charAt(i) && k-->0) res.deleteCharAt(res.length()-1);
res.append(num.charAt(i));
}
if(k>0) res.delete(res.length()-k, res.length());
int s = -1;
while (++s<res.length()&&res.charAt(s)=='0');
String result = res.substring(s, res.length());
return result.equals("") ? "0" : result;
}``````

• Thanks for sharing such nice solution. Here is a Java update one with O(n - k) space.

``````class Solution {
public String removeKdigits(String num, int k) {
if (num.length() <= k) return "0";

int digits = num.length() - k;
char[] stk = new char[digits];
int top = 0;

for (int i = 0; i < num.length(); i++) {
char c = num.charAt(i);
while (top > 0 && stk[top - 1] > c && k > 0) {
k--;
top--;
}

if (top < digits) {
stk[top++] = c;
} else {
/**
* current digit is greater than prev one
* and top has reach the last pos of stk
* then ignor current digit (delete it)
*/
k--;
}
}

int idx = 0;
while (idx < digits && stk[idx] == '0') idx++;
return idx == digits ? "0" : new String(stk, idx, digits - idx);
}
}
``````

• Thanks a lot, I implement this idea with c++

``````class Solution {
public:
string removeKdigits(string num, int k) {
int digitsCnt = num.size() - k;
vector<char> stack;

// push to stack, compare and remove.
if (num.empty())
return string("0");
stack.push_back(num[0]);
for (unsigned i = 1; i < num.size(); i++)
{
char c = stack.back();
while (num[i] < c && k > 0)
{
stack.pop_back();
k--;
// if stack is empty, out while loop
if(stack.empty())
break;
else
c = stack.back();
}
stack.push_back(num[i]);
}

// pick first digitsCnt digits from bottom to up of the stack
vector<char> digits(stack.begin(), stack.begin() + digitsCnt);
unsigned j = 0;
while (!digits.empty() && digits[j] == '0')	// skip leading zero
++j;

// construct result
string result(digits.begin() + j, digits.end());
if (result.empty())
return string("0");
return result;
}
};
``````

• Another solution:

``````string removeKdigits(string num, int k) {
if(k>=num.size())return "0";
string res(1,num[0]);
int i=1;
while(k>0){
if(i==num.size()||res.back()>num[i]){res.pop_back();k--;}
else{
if(res!=""||num[i]!='0')res+=num[i];
i++;
}
}
for(;i<num.size();i++)if(res!=""||num[i]!='0')res+=num[i];
return res==""?"0":res;
}
``````

For more, there is a way to promote this solution, if k<len(num)/2, remove k digits; Else, select len(num)/2-k digits. Such promotion can make Tn=O(n/2)

• @keyulai92gmail.com Could you explain this: new String(stk, idx, digits - idx).
I still cannot get it.Thanks1

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.