O(n) solution


  • 1
    var removeKdigits = function(num, k) {
    
        let i = 0;
        while (i < num.length - 1 && k > 0) {
            if (i === 0 && num[i] === '0') {
                num = num.slice(0, i) + num.slice(i + 1);
            } else if (num[i] > num[i + 1]) {
                num = num.slice(0, i) + num.slice(i + 1);
                i--; k--;
            } else
                i++;
        }
    
        num = num.replace(/^0+/, '');
        return num.slice(0, num.length - k) || '0';
    };
    

  • 1

    Oh, I found even shorter solution, as we can skip === '0' branch.

    var removeKdigits = function(num, k) {
    
        for (let i = 0; i < num.length - 1 && k > 0; i++) {
            if (num[i] > num[i + 1]) {
                num = num.slice(0, i) + num.slice(i + 1);
                i = i - 2; k--;
            }
        }
    
        num = num.replace(/^0+/, '');
        return num.slice(0, num.length - k) || '0';
    };
    

  • 2
    C

    My java version:

    public class Solution {
    public String removeKdigits(String num, int k) {

        for (int i = 0; i < num.length() - 1 && k > 0; i++) {
            if (i >= 0 && num.charAt(i) > num.charAt(i + 1)) {
                num = num.substring(0, i) + num.substring(i + 1);
                i = i - 2; 
                k--;
            }
        }
    
        while(!num.isEmpty() && num.charAt(0) == '0'){
            num = num.substring(1);
        }
        return num.length() - k >= 1 ? num.substring(0, num.length() - k) : "0";
    }
    

    }


  • 0

    What do you mean with "n"? None of these are O(|num|).


  • 0

    @StefanPochmann As I clarified in other thread if you remove letter in O(1) it is O(|num|). Slice of course is not O(1), so you are right this implementation is not O(|num|). If we represent string as doubly linked list we can do O(|num|).
    Your solution with array is better implementation of the same idea.


Log in to reply
 

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