You are given a string s of length n, and an integer k. You are tasked to find the longest subsequence repeated k times in string s.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
A subsequence seq is repeated k times in the string s if seq * k is a subsequence of s, where seq * k represents a string constructed by concatenating seq k times.
"bba" is repeated 2 times in the string "bababcba", because the string "bbabba", constructed by concatenating "bba" 2 times, is a subsequence of the string "bababcba".Return the longest subsequence repeated k times in string s. If multiple such subsequences are found, return the lexicographically largest one. If there is no such subsequence, return an empty string.
Example 1:
Input: s = "letsleetcode", k = 2 Output: "let" Explanation: There are two longest subsequences repeated 2 times: "let" and "ete". "let" is the lexicographically largest one.
Example 2:
Input: s = "bb", k = 2 Output: "b" Explanation: The longest subsequence repeated 2 times is "b".
Example 3:
Input: s = "ab", k = 2 Output: "" Explanation: There is no subsequence repeated 2 times. Empty string is returned.
Constraints:
n == s.length2 <= n, k <= 20002 <= n < k * 8s consists of lowercase English letters.The key idea for #2014 Longest Subsequence Repeated k Times is to find the longest string that can appear as a subsequence of the original string at least k times. First, apply a counting filter: any character used in the answer must appear at least k times in the original string. This significantly reduces the candidate alphabet.
Next, use enumeration with backtracking or BFS to generate candidate subsequences in lexicographic order. For each candidate, check whether repeating it k times forms a subsequence of the original string by scanning through the string greedily. A greedy validation step ensures efficient subsequence checking.
Pruning plays a crucial role: only extend candidates that remain feasible based on character frequencies and subsequence checks. Since the maximum possible length of the result is limited by freq[c] / k, the search space becomes manageable.
This combination of frequency counting, controlled enumeration, and greedy subsequence validation helps solve this otherwise exponential search problem efficiently.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Counting + BFS/Backtracking Enumeration | O(26^L * n) in worst case (pruned heavily in practice) | O(26^L) for candidate generation |
| Subsequence Validation | O(n) per candidate check | O(1) |
Abdul Bari
Use these hints if you're stuck. Try solving on your own first.
The length of the longest subsequence does not exceed n/k. Do you know why?
Find the characters that could be included in the potential answer. A character occurring more than or equal to k times can be used in the answer up to (count of the character / k) times.
Try all possible candidates in reverse lexicographic order, and check the string for the subsequence condition.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Without pruning, enumerating all subsequences would be computationally infeasible. By limiting characters to those with frequency at least k and stopping invalid candidate expansions early, the search space becomes manageable.
Yes, problems involving subsequence generation, pruning, and backtracking patterns are common in FAANG-style interviews. This problem tests string processing, enumeration strategies, and optimization through constraints.
Queues or recursion stacks are commonly used for BFS or backtracking enumeration of candidate subsequences. Simple arrays or hash maps help track character frequencies and assist with pruning during candidate generation.
The common approach combines frequency counting with backtracking or BFS enumeration. Characters that appear fewer than k times are filtered out, and candidate subsequences are generated and validated by checking whether repeating them k times forms a subsequence of the string.