## 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;`

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

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

## Post new comment

• Syntax highlight code surrounded by the `{syntaxhighlighter SPEC}...{/syntaxhighlighter}` tags, where SPEC is a Syntaxhighlighter options string or "class="OPTIONS" title="the title".