Longest Subsequence Repeated k Times solution and explanation

def check(seq, s, k):
    it = iter(s)
    return sum(seq == ''.join(x) for x in zip(*[it] * k)) >= 1

def backtrack(chars, s, k, current):
    if not check(current * k, s, k):
        return ''
    longest = current
    for c in chars:
        candidate = backtrack(chars, s, k, current + c)
        if len(candidate) > len(longest) or (len(candidate) == len(longest) and candidate > longest):
            longest = candidate
    return longest

def longest_subsequence_repeated_k(s, k):
    from collections import Counter
    counter = Counter(s)
    chars = sorted([c for c in counter if counter[c] >= k], reverse=True)
    return backtrack(chars, s, k, '')

import java.util.*;

public class Solution {
    public String longestSubsequenceRepeatedK(String s, int k) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        List<Character> chars = new ArrayList<>();
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            if (entry.getValue() / k > 0) {
                chars.add(entry.getKey());
            }
        }
        Collections.sort(chars, Collections.reverseOrder());
        return backtrack(s, new StringBuilder(), k, chars);
    }

    private String backtrack(String s, StringBuilder current, int k, List<Character> chars) {
        if (!check(s, current.toString(), k)) {
            return "";
        }
        String result = current.toString();
        for (char c : chars) {
            current.append(c);
            String candidate = backtrack(s, current, k, chars);
            current.deleteCharAt(current.length() - 1);
            if (candidate.length() > result.length() || (candidate.length() == result.length() && candidate.compareTo(result) > 0)) {
                result = candidate;
            }
        }
        return result;
    }

    private boolean check(String s, String seq, int k) {
        int seqLen = seq.length();
        int totalLen = seqLen * k;
        if (totalLen > s.length()) {
            return false;
        }
        int j = 0;
        for (int i = 0; i < s.length() && j < totalLen; i++) {
            if (s.charAt(i) == seq.charAt(j % seqLen)) {
                j++;
            }
        }
        return j >= totalLen;
    }
}

#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    string longestSubsequenceRepeatedK(string s, int k) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c] += 1;
        }
        vector<char> chars;
        for (const auto &pair : freq) {
            if (pair.second / k > 0) {
                chars.push_back(pair.first);
            }
        }
        sort(chars.begin(), chars.end(), greater<char>());
        string result = "";
        dfs(chars, s, k, "", result);
        return result;
    }

private:
    void dfs(vector<char> &chars, string &s, int k, string current, string &longest) {
        if (check(s, current, k)) {
            if (current.length() > longest.length() || (current.length() == longest.length() && current > longest)) {
                longest = current;
            }
        }
        for (char c : chars) {
            dfs(chars, s, k, current + c, longest);
        }
    }

    bool check(const string &s, const string &seq, int k) {
        int seqLen = seq.length();
        int j = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == seq[j % seqLen]) {
                j++;
                if (j == seqLen * k) return true;
            }
        }
        return false;
    }
};

const longestSubsequenceRepeatedK = (s, k) => {
    const freqMap = {};
    for (let char of s) {
        if (!freqMap[char]) freqMap[char] = 0;
        freqMap[char]++;
    }
    const chars = Object.keys(freqMap).filter(c => freqMap[c] >= k).sort().reverse();
    let result = '';

    const check = (str, sub, k) => {
        let j = 0;
        for (let i = 0; i < str.length && j < sub.length * k; i++) {
            if (str[i] === sub[j % sub.length]) j++;
        }
        return j >= sub.length * k;
    };

    const dfs = (s, chars, k, current) => {
        if (!check(s, current, k)) return '';
        let longest = current;
        for (let c of chars) {
            let candidate = dfs(s, chars, k, current + c);
            if (candidate.length > longest.length || (candidate.length === longest.length && candidate > longest)) {
                longest = candidate;
            }
        }
        return longest;
    };

    result = dfs(s, chars, k, '');
    return result;
};

function longestSubsequenceRepeatedK(s: string, k: number): string {
    const check = (t: string, k: number): boolean => {
        let i = 0;
        for (const c of s) {
            if (c === t[i]) {
                i++;
                if (i === t.length) {
                    k--;
                    if (k === 0) {
                        return true;
                    }
                    i = 0;
                }
            }
        }
        return false;
    };

    const cnt = new Array(26).fill(0);
    for (const c of s) {
        cnt[c.charCodeAt(0) - 97]++;
    }

    const cs: string[] = [];
    for (let i = 0; i < 26; ++i) {
        if (cnt[i] >= k) {
            cs.push(String.fromCharCode(97 + i));
        }
    }

    const q: string[] = [''];
    let ans = '';
    while (q.length > 0) {
        const cur = q.shift()!;
        for (const c of cs) {
            const nxt = cur + c;
            if (check(nxt, k)) {
                ans = nxt;
                q.push(nxt);
            }
        }
    }

    return ans;
}

func longestSubsequenceRepeatedK(s string, k int) string {
	check := func(t string, k int) bool {
		i := 0
		for _, c := range s {
			if byte(c) == t[i] {
				i++
				if i == len(t) {
					k--
					if k == 0 {
						return true
					}
					i = 0
				}
			}
		}
		return false
	}

	cnt := [26]int{}
	for i := 0; i < len(s); i++ {
		cnt[s[i]-'a']++
	}

	cs := []byte{}
	for c := byte('a'); c <= 'z'; c++ {
		if cnt[c-'a'] >= k {
			cs = append(cs, c)
		}
	}

	q := []string{""}
	ans := ""
	for len(q) > 0 {
		cur := q[0]
		q = q[1:]
		for _, c := range cs {
			nxt := cur + string(c)
			if check(nxt, k) {
				ans = nxt
				q = append(q, nxt)
			}
		}
	}
	return ans
}