O(n) C++ solution with explanation and prove


  • 0

    The idea is to scan the number from leading digit, if the digits are ascending, we continue, till end, if the digit starts to descend, we stop and remove the max digit before descend, hence the last digit of the ascend digit sequence.
    Why this works? Because either you remove the digit before or after the max digit will create a larger number than our current number:
    a. If you remove the digit before, e.g. ki, then the number becomes kn * 10^n + .. + k(i+1) * 10^(i+1) + k(i-1) * 10^i ..
    Notice k(i-1) is greater than ki since it's an ascending sequence, so this number is greater compare with the number in our solution kn * 10^n + .. + k(i+1) * 10^(i+1) + ki * 10^i ..
    b. If you remove the digit after the max digit km, then km is reserved and the number becomes:
    kn * 10^n + .. + km * 10^m ..
    While in our solution, km is removed, the number is kn * 10^n + .. + k(m-1) * 10^m .. since km is the end of ascending sequence and k(m-1) is smaller than km, the number in our solution is obvious smaller.
    c. For the situation the digits in the number keeps ascending and the max digit is the last digit, the prove is the same with case a.

    class solution {
    public:
    	string removeKdigits(string num, int k) {
    		if (num.empty() || k >= num.size())
    		{
    			return "0";
    		}
    
    		int j = 0;
    		for (size_t i = 0; i < k; i++)
    		{	
    			while (j + 1 < num.size() && num[j] <= num[j + 1]) {
    				j++;
    			}
    
    			num.erase(j, 1);
    			while (num.size() > 1 && num[0] == '0') {
    				num.erase(0, 1);
    			}
    			if (j > 0) {
    				j--;
    			}
    		}
    
    		return num;
    	}
    };
    

Log in to reply
 

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