#2014

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Longest Subsequence Repeated k Times

Find the longest subsequence repeated k times in a string using backtracking search with pruning.

string backtracking greedy counting enumeration

Problem Statement

Given a string s and an integer k, you are tasked with finding the longest subsequence repeated exactly k times in s. A subsequence is derived from the string by removing characters while maintaining the original order of the remaining characters.

The problem requires finding the longest subsequence seq such that seq repeated k times is a valid subsequence of s. Your goal is to identify the lexicographically largest subsequence if there are multiple candidates. Note that the length of the longest subsequence will not exceed n/k.

Examples

Example 1

Input: s = "letsleetcode", k = 2

Output: "let"

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"

The longest subsequence repeated 2 times is "b".

Example 3

Input: s = "ab", k = 2

Output: ""

There is no subsequence repeated 2 times. Empty string is returned.

Constraints

n == s.length
2 <= k <= 2000
2 <= n < min(2001, k * 8)
s consists of lowercase English letters.

Solution Approach

Backtracking Search with Pruning

Start with a backtracking search to explore possible subsequences and attempt to form seq repeated k times. Use pruning to discard invalid or unnecessary paths early in the search process.

Greedy Selection for Lexicographical Order

To handle multiple subsequences of the same length, employ a greedy approach to select the lexicographically largest subsequence among the valid options.

Efficient Pruning Strategy

As the subsequence is built, prune paths that cannot possibly lead to a valid sequence repeated k times. This reduces the search space and improves efficiency.

Complexity Analysis

Metric	Value
Time	O(n \cdot {\lfloor \dfrac{n}{k} \rfloor}!)
Space	O(\lfloor \dfrac{n}{k} \rfloor!)

The time complexity is O(n · ⌊n/k⌋!), where n is the length of the string, and ⌊n/k⌋ is the upper limit on the length of the subsequence. The space complexity is O(⌊n/k⌋!), driven by the recursive depth and subsequence storage.

What Interviewers Usually Probe

Can the candidate identify the importance of pruning in reducing the search space?
Does the candidate understand the relationship between subsequence length and k?
How well does the candidate handle lexicographical ordering in the subsequence selection?

Common Pitfalls or Variants

Common pitfalls

Failing to prune search paths that cannot possibly yield valid subsequences.
Overlooking the lexicographical order requirement when multiple valid subsequences exist.
Incorrectly assuming the subsequence length can exceed n/k.

Follow-up variants

Modify the problem to find subsequences repeated m times for a different integer m.
Change the problem to find the shortest subsequence repeated k times.
Consider the case where the subsequence must be contiguous instead of a general subsequence.

FAQ

What is the primary pattern to solve the Longest Subsequence Repeated k Times problem?

The primary pattern is backtracking search with pruning, which explores subsequences efficiently while eliminating unnecessary paths.

How does pruning help in the Longest Subsequence Repeated k Times problem?

Pruning reduces the search space by discarding subsequences that cannot possibly form a valid sequence repeated k times, improving efficiency.

What is the time complexity of the Longest Subsequence Repeated k Times problem?

The time complexity is O(n · ⌊n/k⌋!), where n is the length of the string and ⌊n/k⌋ is the upper bound on subsequence length.

How do you handle lexicographical order in this problem?

Use a greedy strategy to select the lexicographically largest subsequence when multiple subsequences of the same length are possible.

What does it mean for a subsequence to be repeated k times?

A subsequence is repeated k times if concatenating the subsequence k times results in a valid subsequence of the string s.

terminal

Solution

Solution 1: BFS

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 $\textit{cs}$ in ascending order. Next, we can use BFS to enumerate all possible subsequences.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        def check(t: str, k: int) -> bool:
            i = 0
            for c in s:
                if c == t[i]:
                    i += 1
                    if i == len(t):
                        k -= 1
                        if k == 0:
                            return True
                        i = 0
            return False

        cnt = Counter(s)
        cs = [c for c in ascii_lowercase if cnt[c] >= k]
        q = deque([""])
        ans = ""
        while q:
            cur = q.popleft()
            for c in cs:
                nxt = cur + c
                if check(nxt, k):
                    ans = nxt
                    q.append(nxt)
        return ans

Continue Practicing

#2048 next greater numerically balanced number #2131 longest palindrome by concatenating two letter words #1849 splitting a string into descending consecutive values