Longest Subsequence Repeated k Times - Video Solutions

Problem Overview: Given a string s and an integer k, find the longest subsequence that appears at least k times in s. The subsequences can overlap, but the order of characters must remain the same. If multiple answers exist with the same length, return the lexicographically largest one.

Approach 1: Backtracking with Pruning (Time: roughly O(26^m * n), Space: O(m))

This approach treats the result as a candidate string and builds it character by character using backtracking. First count character frequencies using counting. A character can only appear in the answer if its frequency in s is at least k. Build candidates using only those valid characters. During recursion, append a character, then check whether the candidate repeated k times is still a subsequence of s. If it fails, prune that branch immediately. This pruning drastically reduces the search space because invalid prefixes never expand further. To check subsequences efficiently, iterate through s and greedily match characters.

The key insight: the maximum length of the answer is small because each character must appear at least k times in the string. That constraint keeps the search manageable. Backtracking also tries characters in reverse lexicographic order so the first valid longest candidate becomes the final answer.

Approach 2: Iterative Search with Pre-filtering (Time: ~O(C^m * n), Space: O(C))

This method avoids deep recursion and instead performs iterative candidate expansion. Start by computing frequencies of characters in the string. Only characters with frequency ≥ k are allowed in the candidate pool. Build possible subsequences level by level: start with single characters, then extend them by appending valid characters. For every candidate, check whether repeating it k times forms a subsequence of s. Invalid candidates are discarded early.

The greedy element appears when exploring candidates in descending lexicographic order. Since the goal is the longest and lexicographically largest subsequence, maintaining that ordering ensures better candidates are evaluated first. Pre-filtering significantly reduces the alphabet size, which keeps the enumeration manageable.

This iterative search works well in languages like C++ or JavaScript where queue-based enumeration is straightforward and recursion limits might be undesirable. The subsequence validation step still uses a linear scan over s, matching characters in order.

Recommended for interviews: Backtracking with pruning is the approach most interviewers expect. It demonstrates understanding of subsequence validation, search space reduction, and frequency-based pruning. The iterative enumeration variant shows the same idea implemented without recursion and is useful when discussing optimization or language-specific constraints.