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.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.
Java
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.
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.
| 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. |
4.9 Longest Common Subsequence (LCS) - Recursion and Dynamic Programming • Abdul Bari • 1,257,418 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