leetcode.com – Next Closing Time

I’ve been having problems with recursive problems lately so I’ve been studying them. I found a good one on leetcode.com(2) and I want to document it.

Question:
Given a time represented in the format “HH:MM”, form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

 

You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9″ are all invalid.”

Problem #1:
“13:94”

 

I pretty quickly launched into a permutation solution and eventualy realized I had missed the fact that the numbers are repeatable which put a big kink in my non-repeating-characters permutation. I relented into poking around online to see what others are doing in this situation. I eventually came across the following tree for lexicological string permutations (1)

                              data=””
                            /            \
                          /                \
                        /                    \
                   index=0                index=0
                   i=0                          i=1
                  data=”A”                 data=”B”
                  /          \                  /           \
                /              \               /              \
             index=1      index=1    index=1    index=1
               i=0               i=1        i=0            i=1
            data=”AA”  data=”AB”  data=”BA”  data=”BB”

And this helped me create a visual for what I needed to do. Thinking in terms of linked list I wanted to run down the tree all the way to left first so 1, 1, 1, 1 then 1, 1, 1, 3; 1, 1, 1, 9 etc etc. Once I had it visualized in my mine the recursive code was a lot easier to come up with:

– recursive function w options, current value, and storage array
– return on value > 2400 or value.slice(2) > 60 to only generate valid times
– loop prepend through every option every recurse until the option length and value length match, add value to storage

After taking care of some edge cases, here’s what I ended up with:

function permNum(opts, cur="", purse=[]) { // str="1934"; it=0; purse=[];
   if(+cur >= 2400 || +(cur.slice(2)) >= 60) return purse;

    if(cur.length >= opts.length) {
       purse.push(cur);
       return purse;
   }

   var str = "";
   for(var i = 0; i < opts.length; ++i) {
       str = opts[i];
        permNum(opts, cur+str, purse);
   }
   return purse;
}

var nextClosestTime = function(time) { // time="19:34"
   var timeStr = time.replace(":",""); // timeStr="1934"
   var perms = permNum(timeStr);

    //console.log(perms);

    var min = 99999;
   for(var o of perms) {
       var diff = +o - +timeStr;
       if(diff > 0 && diff < min) min = diff;
   }

    var nTime = String(+timeStr + +min);
   if(min >= 99999) nTime = perms[0];

    while(nTime.length < timeStr.length) {
       nTime = "0" + nTime;
   }

    return nTime.slice(0, 2) + ":" + nTime.slice(2);
}

 

Citation:
1) http://www.geeksforgeeks.org/print-all-permutations-with-repetition-of-characters/
2) https://leetcode.com/problems/next-closest-time/description/