Got this problem from Codewars.
There is a secret string which is unknown to you. Given a collection of random triplets from the string, recover the original string.
A triplet here is defined as a sequence of three letters such that each letter occurs somewhere before the next in the given string. "whi" is a triplet for the string "whatisup".
As a simplification, you may assume that no letter occurs more than once in the secret string.
You can assume nothing about the triplets given to you other than that they are valid triplets and that they contain sufficient information to deduce the original string. In particular, this means that the secret string will never contain letters that do not occur in one of the triplets given to you.
For example, given triplets [['t','u','p'], ['w','h','i'], ['t','s','u'], ['a','t','s'], ['h','a','p'], ['t','i','s'], ['w','h','s']]
, the code should return the string whatisup
. All the context that I had to solve the problem came from the description. This is a programming challenge, not meant to solve a real life problem. My code passed the tests. There where no random tests though. My main interest is about performance.
function recoverSecret(triplets) {
const after = {};
const precedence = (a, b) => after[a].has(b)
|| [...after[a]].some(c => precedence(c, b) == -1) ? -1 : 1;
for (let triplet of triplets) {
after[triplet[0]] = new Set([...(after[triplet[0]] || []), ...triplet.slice(1)]);
after[triplet[1]] = new Set([...(after[triplet[1]] || []), triplet[2]]);
after[triplet[2]] = new Set([...(after[triplet[2]] || [])]);
}
return Object.keys(after).sort(precedence).join``;
}
Tried destructuring triplet
into [a, b, c]
to make it more readable, but got execution timeout. Codewars platform has a max time limit of 12000ms. Wanted to do this:
for (let [a, b, c] of triplets) {
after[a] = new Set([...(after[a] || []), b, c]);
after[b] = new Set([...(after[b] || []), c]);
after[c] = new Set([...(after[c] || [])]);
}