9ms simple to understand c++ Soln. with comments and idea behind the approach.


  • 0
    S
    //REMOVE K DIGITS
    /*Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
    Note:
    The length of num is less than 10002 and will be ≥ k.
    The given num does not contain any leading zero.
    */
    
    class Solution {
    public:
        string removeKdigits(string num, int k) {
        	//special case to handle if k > number of digits given in the string.
            if(k>=num.length())
                return "0";
            if(!k)
                return num;
    
      		vector<int> st;
      		st.push_back(num[0]-'0');
    //insert digits into the stack only if its greater than the element at the top of the stack, or else you keep popping elements from the stack until you satisfy the condition. This is implemented by the while loop.
      		for(int i=1;i<num.length();i++){
      			while(k && st[st.size()-1]>num[i]-'0'){
      				st.pop_back();
      				--k;
      			}
      			st.push_back(num[i]-'0');
      		
      		}
      //This is to handle special case when all digits are the same,the length of the stack would be the same as the length of the string, in that case you have to pop elements from the stack until it becomes equal to the length string length-k .		
      		while(st.size()>num.size()-k){
      		    st.pop_back();
      		}
      	/* the further statements are to parse the output string so that it doesnt contain any leading zeros*/	    
      		num="";
      		std::reverse(st.begin(),st.end());
      		for(int i=st.size()-1;i>=0;i--){
      		    if(st[i]>0)
      		        break;
      		    else
      		        st.pop_back();
      		}
      		if(!st.size())
      		    return "0";
      		for(int i=st.size()-1;i>=0;i--){
      		    num+=st[i]+'0';
      		}
      		return num;
        }
    };
    

Log in to reply
 

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