Java O(n) without extra space


  • 0
    C

    Traverse all digits till you found a number smaller than previous number and delete this number from the string.
    If all the numbers in a string are increasing order than delete 'k' digits from the end.

    public String removeKdigits(String num, int k) {
    int i=0;
    if(num.length()<=k){
    return “0”;
    }
    while(i<num.length()-1 && k>0){
    char curr = num.charAt(i);
    char next = num.charAt(i+1);
    int cInt = Character.getNumericValue(curr);
    int nInt = Character.getNumericValue(next);
    if(nInt < cInt){
    String prevStr = num.substring(0,i);
    String nextStr = num.substring(i+1,num.length());
    num = prevStr+nextStr;
    if(i>0)
    i=i-1;
    k–;
    }else
    i++;
    }
    if(k>0){
    while(k>0){
    num = num.substring(0,num.length()-1);
    k–;
    }
    }
    while(num.charAt(0)==‘0’ && num.length()>1){
    num = num.substring(1,num.length());
    }
    return num;
    }
    

Log in to reply
 

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