Leetcode 402: remove k digits

It is so time consuming to write the solution and make it work. The idea is simple, using bucket sorting and slide window to find minimum number.

Here is the link.

June 27, 2019

It is tough experience to write the solution using slide window and bucket sort in order to lower time complexity O(N), N is the length of string.

Case study 1: 5337, k = 2

For example, number is 5337, k = 2, slide window size is Math.Max( k + 1, num.Length), since there are 10 digits from 0 to 9, it is easy to find minimum digit in the slide window by going over buckets with size 10 one by one.

Go over example 5337, first slide window 533, the minimum digit is 3, and then next slide window we can need to move first digit 5 out of window, and add digit 7 into the window. Two arithmetic calcultions are needed.

The smallest number should be 33, somehow, my practice showed 533 because I forgot to remove first digit 5 in slide window bucket.

Case study: Slide window design

Two varaibles: start, end
Window size: maximum is k + 1
Bucket sort is applied to slide window first time, and then when every time the window slides, only leftmost digit will be removed out of the window; if window has width less than k + 1, next digit will be added to window. Also k will be changed when every digit is removed.

Case study: My practice code run into deadloop

I did not pay attention how to write a while loop to avoid deadloop.

smallestDigit - skip digit until smallest digit is met, I design a while loop with no break statement at the beginning. And it does not work for the first digit is smallest one.

Number is 12345, k = 2.

It is so easy to miss edge cases, confuse one variable with others. There are so many places to go wrong. My practice took me more than 90 minutes. So I believe that using bucket sort and slide window idea does not work for me. I will have to push hard to learn to write bug free code in less than 20 minutes.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _402_remove_k_digits
{
    class Program
    {
        static void Main(string[] args)
        {
            //var result = RemoveKdigits("543213", 2);
            //var result2 = RemoveKdigits("1432219", 3);
            var result3 = RemoveKdigits("5337", 2); 
        }

        /// <summary>
        /// use sliding window, bucket sort idea
        /// </summary>
        /// <param name="number"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static string RemoveKdigits(string number, int k)
        {
            if (number == null || number.Length < k)
                return string.Empty;

            if (k == number.Length)
                return "0";

            var digits = new int[10];
            var length = number.Length;
            var start = 0;
            var end   = Math.Min(k, length - 1); /* caught by debugger, slide window size maximum is k + 1. */

            for (int i = start; i < end + 1; i++)
            {
                var digit = number[i] - '0'; // add - '0'
                digits[digit]++;
            }

            var smallestLength = length - k; // k is changable, so need to declare a variable
            var smallest = new StringBuilder();

            while (start < length)
            {
                var smallestDigit = -1;
                
                for (int digit = 0; digit <= 9; digit++)
                {
                    var count = digits[digit];
                    if (count > 0)
                    {
                        smallest.Append((char)(digit + '0'));
                        digits[digit]--;
                        smallestDigit = digit;  // caught by debugger  
                        break;
                    }                    
                }

                // remove digits 
                // smallestDigit - skip digit until smallest digit is met
                int index = start;
                while (index < length && k > 0)
                {
                    var value = number[index];
                    var digit = value - '0';
                       
                    if (digit == smallestDigit)
                    {
                        break;
                    }

                    digits[digit]--; // caught by debugger

                    start++;
                    index++;
                    k--;                                            
                }                

                // skip one more
                start++;

                // make sure the size of window is K + 1
                while ((end - start + 1) < (k + 1) && (end + 1) < length)
                {
                    digits[number[end + 1] - '0']++;
                    end++;
                }

                // no more chars to be added - break
                if (smallest.ToString().Length == smallestLength)
                    break;

                // no more chars to remove - edge
                if (k == 0)
                {
                    for (int i = start; i < length; i++)
                    {                        
                        smallest.Append(number[i]);                       
                    }

                    break;
                }                
            }

            // remove leading zero
            var removeLeadingZeoro = new StringBuilder();
            var leadingZero = true;
            for (int i = 0; i < smallest.Length; i++)
            {
                if (leadingZero && smallest[i] == '0')
                {
                    continue;
                }                
                
                leadingZero = false;
                removeLeadingZeoro.Append(smallest[i]);                
            }

            // return "0" intead of ""
            return removeLeadingZeoro.Length == 0 ? "0" : removeLeadingZeoro.ToString();
        }
    }
}