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.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.
This approach constructs possible subsequences character by character using backtracking. We try potential subsequences in a lexicographical order and if a subsequence can be repeated k times and is still a subsequence of s, we record it.
We use a recursive function to generate possible subsequences, trying to append characters in a way that ensures the subsequences generated remain valid candidates. Each generated candidate is verified by checking if it can form a subsequence that repeats k times.
The backtracking function is implemented to explore all possible subsequences. We use a helper function check to determine if a candidate subsequence can repeat k times within s. The characters are sorted in reverse lexicographical order to ensure we find the lexicographically largest subsequence.
Time Complexity: O(2^n), where n is the length of the string due to the generation of subsequences.
Space Complexity: O(n) due to recursion and additional data structures.
This approach begins by pre-filtering characters and possible subsequences based on their frequency in s. Then it uses an iterative search to evaluate each candidate, starting from the most frequently appearing characters and growing subsequences by iteratively adding characters.
The sequence group is filtered and expanded iteratively to ensure that invalid paths are quickly discarded, making the search efficient.
The method first constructs a list of characters that can be part of the repeated subsequence. A depth-first search (DFS) approach is used to evaluate potential subsequences. For each subsequence, we use a check function to verify if it can be a k-repeated subsequence of the given string.
C++
JavaScript
Time Complexity: O(2^n), due to the iterative exploration of subsequences.
Space Complexity: O(n) because of the recursion stack and additional data structures used.
We can first count the occurrences of each character in the string, and then store the characters that appear at least k times in a list cs in ascending order. Next, we can use BFS to enumerate all possible subsequences.
We define a queue q, initially putting the empty string into the queue. Then, we take out a string cur from the queue and try to append each character c \in cs to the end of cur to form a new string nxt. If nxt is a subsequence that can be repeated k times, we add it to the answer and put nxt back into the queue for further processing.
We need an auxiliary function check(t, k) to determine whether the string t is a repeated k times subsequence of string s. Specifically, we can use two pointers to traverse s and t. If we can find all characters of t in s and repeat this process k times, then return true; otherwise, return false.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking with Pruning | Time Complexity: O(2^n), where Space Complexity: O(n) due to recursion and additional data structures. |
| Approach 2: Iterative Search with Pre-filtering | Time Complexity: O(2^n), due to the iterative exploration of subsequences. Space Complexity: O(n) because of the recursion stack and additional data structures used. |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | ~O(26^m * n) | O(m) | Best general solution. Pruning removes invalid prefixes early and works well when candidate length is small. |
| Iterative Search with Pre-filtering | ~O(C^m * n) | O(C) | Good when avoiding recursion or implementing breadth-first enumeration in C++/JavaScript. |
Longest Subsequence Repeated k Times | 2 Ways To Code | Detailed | Leetcode 2014 | codestorywithMIK • codestorywithMIK • 10,329 views views
Watch 9 more video solutions →Practice Longest Subsequence Repeated k Times with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor