Java Greedy Solution, with explanation


  • 0
    Z

    If look to the problem from slightly "different angle", we can mention that the problem can be reformulated as, 'select (num.length() - k) consecutive digits from the given sequence, so the resultant number is the minimum possible'. Now, that reformulation allows us to solve it by greedy approach. At last, non-formally saying, the algorithm consists of the following steps:

    1. Find out the number of digits must be selected. i.e d = num.length() - k
    2. Select for each position the minimum possible digit. To do so, keep in mind, that digits for each position could be selected from range between index of previously selected digit and num.length()-pos.
      For example, process of selecting 4 digits from sequence "1432219", can be interpreted as follows:
      First digit can be selected from range [0, 3], so the minimum is 1
      Second digit can be selected from range [1,4] , so the minimum is 2
      Third digit can be selected from range [4, 5], so the minimum is 1
      The last digit can be selected from range [5,5], so the minimum is 9
      As a result, we get number 1219, the minimum possible number after removing 3 digits from the original sequence.

    Node, that after completion of the above steps it is necessary to eliminate leading zeros.
    Time complexity of the algorithm is O((n-k)*k) and space complexity is O(n-k)

    public class Solution {
        public String removeKdigits(String num, int k) {
            if(k == num.length()) return "0";
            int d = num.length()-k;
            StringBuilder ans = new StringBuilder();
            int l = 0;
            for(int j = d;j>0;j--){
                int r = num.length()-j;
                int minIndex = 0;
                int min = Integer.MAX_VALUE;
                for(int jj =l;jj<=r;jj++){
                    if(num.charAt(jj)-'0'<min){
                        min = num.charAt(jj)-'0';
                        minIndex = jj;
                    }
                }
                l = minIndex+1;
                ans.append((num.charAt(minIndex)));
            }
            String res = ans.toString();
            int j = 0;
            while(j<res.length() && res.charAt(j) == '0'){
                j++;
            }
            if(j == res.length()) return "0";
            return res.substring(j, res.length());
        }
    }

Log in to reply
 

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