[LeetCode] Remove K Digits

402. Remove K Digits

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.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

new solution update 2022.02.18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
string removeKdigits(string s, int k) {
if(s.length() == k) return "0";
string res = "";
for(int i = 0; i < s.length(); i++) {
while(res.length() > 0 and k > 0 and res.back() > s[i]) {
k--;
res.pop_back();
}
res += s[i];
if(res == "0") res.pop_back();
}

while(k and res.length()) {
k--;
res.pop_back();
}

return res.length() == 0 ? "0" : res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
private:
char getMinimum(map<char,list<int>> &chars, int maxPos) {
int res = 10;
for(auto p : chars) {
if(!p.second.empty() && (p.first & 0b1111) < res && p.second.front() <= maxPos)
res = (p.first & 0b1111);
}
return res | 0b110000;
}
public:
string removeKdigits(string num, int k) {
if(k == 0)
return num;
if(k == num.length())
return "0";
stringstream res;
map<char, list<int>> chars;
int pos, prev = -1, len = 0;
for(pos = 0; pos <= k + 1; pos++) {
chars[num[pos]].push_back(pos);
}

while(len != num.length() - k) {
char choosed = getMinimum(chars, k + len);
for(int i = chars[choosed].front() + k; i > 0 && pos < num.length(); i--, pos++) {
chars[num[pos]].push_back(pos);
}

prev = chars[choosed].front();

for(auto p = chars.begin(); p != chars.end(); p++) {
while(!p->second.empty() && p->second.front() <= prev) {
p->second.pop_front();
}
}

res<<choosed;
len++;
if(num.length() - prev - 1 == num.length() - k - len) {
res<<num.substr(prev + 1);
break;
}
}
string ret = res.str();
for(pos = 0; pos < ret.length() && ret[pos] == '0'; pos++) {}
if(pos != 0)
ret = ret.substr(pos);
return ret == "" ? "0" : ret;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/01/24/PS/LeetCode/remove-k-digits/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.