Algorithm
Problem Name: 402. Remove K Digits
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
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.
Constraints:
1 <= k <= num.length <= 105numconsists of only digits.numdoes not have any leading zeros except for the zero itself.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
char* removeKdigits(char* num, int k) {
int i, j, l;
l = strlen(num);
while (k > 0 && *num) {
while (*num == '0') { // remove leading zeros
num ++;
l --;
}
i = 0;
while (i < l - 1 && num[i] <= num[i + 1]) {
i ++;
}
// take out the i-th one
for (j = i; j < l - 1; j ++) {
num[j] = num[j + 1];
}
num[j] = 0;
l --;
k --;
}
while (*num == '0') { // remove leading zeros
num ++;
}
if (!*num) num = "0";
return num;
}
Input
num = "1432219", k = 3
Output
"1219"
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string removeKdigits(string num, int k) {
int n = num.size(), remain = n - k;
if(remain == 0) return "0";
string s = "";
for(auto x: num){
while(n > remain && !s.empty() && s.back() - '0' > x - '0'){
s.pop_back();
n--;
}
s.push_back(x);
}
int i = 0;
while(i < s.size() && s[i] == '0') i++;
return s.substr(i, remain) == "" ? "0" : s.substr(i, remain>;
}
};
Input
num = "1432219", k = 3
Output
"1219"
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String removeKdigits(String num, int k) {
LinkedList stack = new LinkedList<>();
for (char c : num.toCharArray()) {
while (!stack.isEmpty() && k > 0 && stack.peekLast() > c) {
stack.removeLast();
k--;
}
stack.addLast(c);
}
while (k-- > 0) {
stack.removeLast();
}
StringBuilder sb = new StringBuilder();
boolean currZero = true;
for (char c : stack) {
if (currZero && c == '0') {
continue;
}
currZero = false;
sb.append(c);
}
return sb.length() == 0 ? "0" : sb.toString();
}
}
Input
num = "10200", k = 1
Output
"200"
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const removeKdigits = function(num, k) {
const digits = num.length - k;
const stk = new Array(num.length);
let top = 0;
for (let i = 0; i < num.length; i++) {
let c = num.charAt(i);
while (top > 0 && stk[top - 1] > c && k > 0) {
top -= 1;
k -= 1;
}
stk[top++] = c;
}
let idx = 0;
while (idx < digits && stk[idx] === "0") idx++;
return idx === digits ? "0" : stk.slice(idx, digits + idx).join("");
};
Input
num = "10200", k = 1
Output
"200"
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def removeKdigits(self, num, k):
out = []
for digit in num:
while k and out and out[-1] > digit:
out.pop()
k -= 1
out.append(digit)
return ''.join(out[:-k or None]).lstrip('0') or "0"
Input
num = "10", k = 2
Output
"0"
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Text;
namespace LeetCode
{
public class _0402_RemoveKDigits
{
public string RemoveKdigits(string num, int k)
{
if (k == 0) return num;
if (k == num.Length) return "0";
var stack = new Stack < char>();
foreach (var ch in num)
{
while (k > 0 && stack.Count > 0 && ch < stack.Peek())
{
k--;
stack.Pop();
}
stack.Push(ch);
}
while (k-- > 0 && stack.Count > 0)
stack.Pop();
if (stack.Count == 0) return "0";
var sb = new StringBuilder();
foreach (var ch in stack)
sb.Append(ch);
var result = new StringBuilder();
bool leadingZero = true;
for (int i = sb.Length - 1; i >= 0; i--)
{
if (leadingZero && sb[i] == '0') { continue; }
leadingZero = false;
result.Append(sb[i]);
}
return result.Length > 0 ? result.ToString() : "0";
}
}
}
Input
num = "10", k = 2
Output
"0"