🐳Longest Subsequence Repeated k Times – LeetCode 2014 (C++ | Python | JavaScript) – ██FR█████ █INTELL███████████

This content originally appeared on DEV Community and was authored by Om Shree

Hey, algorithm adventurers!

Today we’re unraveling a brain-bending string manipulation puzzle — LeetCode 2014: Longest Subsequence Repeated k Times. This one’s a cocktail of greedy character selection, frequency filtering, and backtracking. If you love recursion, this one will scratch that itch. Let’s dive in!

Problem Summary

You’re given:

A string s
An integer k

You must find the longest subsequence that:

Can be repeated k times (i.e., seq * k) and still be a subsequence of s.
Is lexicographically the largest if multiple options exist.

Return the resulting subsequence or an empty string if none exists.

Intuition

This problem is a combination of:

Character frequency analysis: If a character appears less than k times, it cannot contribute.
Backtracking: Try constructing subsequences in reverse lexicographic order ('z' → 'a').
Validation: Check whether a given sequence repeated k times is still a subsequence of s.

By pruning unqualified characters and recursively building candidates, we can search efficiently.

Approach

Count the frequency of all characters in s.
Filter out characters that appear fewer than k times.
Use backtracking to try adding characters (from 'z' to 'a') to form a candidate seq.
For each seq, check whether seq * k is a valid subsequence of s.
Track the longest valid result.

C++ Code

class Solution {
public:
    string longestSubsequenceRepeatedK(string s, int k) {
        vector<int> cnts(26);
        for (char c : s) ++cnts[c - 'a'];

        string new_s;
        for (char c : s) {
            if (cnts[c - 'a'] >= k) new_s += c;
        }

        string result, curr;
        backtrack(new_s, k, curr, cnts, result);
        return result;
    }

private:
    void backtrack(const string& s, int k, string& curr, vector<int>& cnts, string& result) {
        if (!check(s, k, curr)) return;
        if (curr.size() > result.size()) result = curr;

        for (char c = 'z'; c >= 'a'; --c) {
            if (cnts[c - 'a'] < k) continue;
            cnts[c - 'a'] -= k;
            curr += c;
            backtrack(s, k, curr, cnts, result);
            curr.pop_back();
            cnts[c - 'a'] += k;
        }
    }

    bool check(const string& s, int k, const string& curr) {
        if (curr.empty()) return true;
        int i = 0, count = 0;
        for (char c : s) {
            if (c == curr[i]) {
                if (++i == curr.size()) {
                    if (++count == k) return true;
                    i = 0;
                }
            }
        }
        return false;
    }
};

JavaScript Code

var longestSubsequenceRepeatedK = function(s, k) {
    const count = Array(26).fill(0);
    for (let ch of s) count[ch.charCodeAt(0) - 97]++;

    const filtered = [...s].filter(ch => count[ch.charCodeAt(0) - 97] >= k).join('');
    let result = "";

    const backtrack = (curr) => {
        if (!isValid(filtered, curr, k)) return;
        if (curr.length > result.length || (curr.length === result.length && curr > result)) {
            result = curr;
        }

        for (let c = 25; c >= 0; c--) {
            if (count[c] < k) continue;
            count[c] -= k;
            backtrack(curr + String.fromCharCode(c + 97));
            count[c] += k;
        }
    };

    const isValid = (s, seq, k) => {
        if (seq.length === 0) return true;
        let i = 0, count = 0;
        for (let ch of s) {
            if (ch === seq[i]) {
                if (++i === seq.length) {
                    if (++count === k) return true;
                    i = 0;
                }
            }
        }
        return false;
    };

    backtrack("");
    return result;
};

Python Code

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        from collections import Counter
        cnt = Counter(s)
        usable = [c for c in s if cnt[c] >= k]
        result = ''

        def isValid(seq):
            i = count = 0
            for c in usable:
                if c == seq[i]:
                    i += 1
                    if i == len(seq):
                        count += 1
                        if count == k:
                            return True
                        i = 0
            return False

        def backtrack(curr, freq):
            nonlocal result
            if not isValid(curr): return
            if len(curr) > len(result) or (len(curr) == len(result) and curr > result):
                result = curr
            for i in reversed(range(26)):
                c = chr(ord('a') + i)
                if freq[c] >= k:
                    freq[c] -= k
                    backtrack(curr + c, freq)
                    freq[c] += k

        backtrack('', cnt.copy())
        return result

Key Notes

Uses reverse lexicographic order to prioritize larger strings first.
Prunes search space by skipping characters with insufficient frequency.
Efficient despite recursive structure due to aggressive filtering.

Final Thoughts

This problem challenges your mastery over subsequences, string frequency, and recursion. While the brute force space is enormous, the smart use of pruning and backtracking makes this approach efficient and elegant.

Drop a if this clarified the problem, and stay tuned for more deep-dive articles!

Happy coding!

This content originally appeared on DEV Community and was authored by Om Shree