Longest Subsequence Repeated k Times LeetCode solution in JavaScript

1
// Idea comes from:
2
// https://leetcode.com/problems/longest-subsequence-repeated-k-times/discuss/1471930/Python-Answer-is-not-so-long-explained
3

4
var longestSubsequenceRepeatedK = function (s, k) {
5
  const freq = {};
6
  for (const c of s) {
7
    if (!freq[c]) freq[c] = 0;
8
    freq[c]++;
9
  }
10

11
  // Find hot string
12
  let hot = "";
13
  for (const [c, cnt] of Object.entries(freq)) {
14
    const repeat = Math.floor(cnt / k);
15
    hot += c.repeat(repeat);
16
  }
17

18
  // Find all subset and permutation of hot string
19
  let targets = new Set();
20
  const subsets = getSubset(hot);
21
  for (const subset of subsets) {
22
    const permutations = getPermutation(subset);
23
    for (const per of permutations) targets.add(per);
24
  }
25

26
  // Sort targets by length and lexico
27
  targets = [...targets].sort((a, b) => {
28
    const delta = b.length - a.length;
29
    if (delta) return delta;
30
    return b.localeCompare(a);
31
  });
32

33
  // Filter s and check subsequence
34
  s = [...s].filter((c) => hot.includes(c)).join("");
35
  for (const tar of targets) {
36
    if (isSubsequence(s, tar.repeat(k))) return tar;
37
  }
38

39
  return "";
40
};
41

42
function getSubset(str) {
43
  const res = [""];
44
  for (const c of str) {
45
    res.push(...res.map((curStr) => curStr + c));
46
  }
47
  return [...new Set(res)];
48
}
49

50
function getPermutation(str) {
51
  let res = [""];
52
  for (const c of str) {
53
    const resT = [];
54
    for (const cur of res) {
55
      for (let i = 0; i <= cur.length; i++) {
56
        const curT = cur.substring(0, i) + c + cur.substring(i);
57
        resT.push(curT);
58
      }
59
    }
60
    res = resT;
61
  }
62
  return [...new Set(res)];
63
}
64

65
function isSubsequence(s, t) {
66
  let i = 0;
67
  for (let j = 0; j < s.length; j++) {
68
    if (t[i] === s[j]) {
69
      i++;
70
      if (i === t.length) return true;
71
    }
72
  }
73
  return false;
74
}