Short 10 lines O(n) Java Code


  • 5
    Z

    Basically remove those digits start descending
    O(n) Time O(n) space

    public class Solution {
        public static String removeKdigits(String num, int k) {
            StringBuilder sb = new StringBuilder();
            for(char c : num.toCharArray()) {
                while(k > 0 && sb.length() != 0 && sb.charAt(sb.length() - 1) > c) {
                    sb.setLength(sb.length() - 1);
                    k--;
                }
                if(sb.length() != 0 || c != '0') sb.append(c);  // Only append when it is not leading zero
            }
            if(k >= sb.length()) return "0";
            sb.setLength(sb.length() - k);  // use all remaining k
            return sb.toString();  
        }
    }
    

  • 0
    J

    @zehua2 Good solution, but it seems there is a little bug in the line 11.

    if(k <= sb.length()) sb.setLength(sb.length() - k);
    

    For test "1002", 3, your answer will be "2", while the correct answer should be "0".
    That is because after scanning the string num, sb = "2", k = 2, but we should still remove "2" from sb.

    So after scanning, if k > 0, we should remove elements from sb with the number of min(k, sb.length())

    Thus we should modify line 11 as:

    if(k > 0) sb.setLength(sb.length() - Math.min(k, sb.length()));
    

  • 0
    Z

    @JieJackyZhang Thanks for your comment! I have revised my code.


Log in to reply
 

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