Saturday, September 24, 2016

Solution to Leetcode 402 Remove K Digits

Problem Statement could be found @https://leetcode.com/problems/remove-k-digits/

Approach - Idea is to start from first character of string and compare it with next character, if current character is smaller then next then it can be removed. If the very first  character is larger than second then remove it. All the while take care of zeros at the start

Following is the code
class Solution {
public:
    string truncZero(string num){
         while (num.size() > 1 && num.at(0) == '0'){
                num = num.substr(1);
         }
        return num;  
    }
    string removeKdigits(string num, int k) {
     
       
        while ( k >0){
            while (num.size() !=0 && num.at(0) == '0'){
                num = num.substr(1);
            }
            int length = num.size();
            if (length == 0){
                num = "0";
            }
            bool flag=  false;
            for (int i=0;i<length-1;i++){
               
                if ((num.at(i) ) > (num.at(i+1) )){
                    flag=  true;
                    if ( i == 0){
                        num = num.substr(1);
                       
                    }else{
                       
                        string tempStr = num.substr(0,i) ;
                        if ((i+1) < num.size()){
                           tempStr = tempStr + num.substr((i+1));
                        }
                        num = tempStr;
                    }
                    break;
                }
            }
            if (flag == false){
                num = num.substr(0,num.size()-1);
            }
           
            k--;
        }

        if (num.size() == 0)
            num = "0";
        if (num.size() > 1){
            num = truncZero(num);
        }
        return num;
    }
};