{x}
blog image

Longest Subsequence Repeated k Times

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.

  • For example, "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:

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.length
  • 2 <= n, k <= 2000
  • 2 <= n < k * 8
  • s consists of lowercase English letters.

Solution Explanation for Longest Subsequence Repeated k Times

This problem asks to find the lexicographically largest longest subsequence that is repeated k times within a given string s. The naive approach of generating all subsequences and checking for repetitions is computationally expensive. A more efficient approach uses a combination of backtracking and counting.

Approach:

  1. Backtracking: We employ a backtracking algorithm to explore all possible subsequences of the input string s. The backtracking function recursively builds subsequences by either including or excluding each character.

  2. Counting Occurrences: For each generated subsequence, we need to efficiently count how many times it occurs as a subsequence within s. We can achieve this using dynamic programming. Let dp[i][j] represent whether the subsequence sub (up to index j) is a subsequence of s (up to index i). The base case is dp[i][0] = True for all i (empty subsequence is always a subsequence). The recurrence relation is:

    dp[i][j] = dp[i-1][j] or (s[i-1] == sub[j-1] and dp[i-1][j-1])

    This means the subsequence sub up to index j is a subsequence of s up to index i if either:

    • It was already a subsequence of s up to index i-1 (excluding the current character in s).
    • The current character in s matches the current character in sub, and sub (up to index j-1) was a subsequence of s (up to index i-1).

  3. Checking Repetition: After calculating dp[n][len(sub)] (where n is the length of s and len(sub) is the length of the subsequence), if dp[n][len(sub)] is true, it means the subsequence sub appears at least once. We repeat this process to count the number of times the subsequence appears. This can be optimized by iterating only through indices in s that are potentially part of the subsequence

  4. Lexicographical Ordering: The algorithm keeps track of the lexicographically largest longest subsequence found so far that repeats k times.

Code (Python):

def longestSubsequenceRepeatedK(s, k):
    n = len(s)
    best = ""
 
    def count_subsequence(sub):
        count = 0
        indices = []
        for i in range(n):
          if s[i] == sub[0]:
            indices.append(i)
 
        for i in indices:
            dp = [[False] * (len(sub) + 1) for _ in range(n + 1)]
            for i1 in range(n + 1):
              dp[i1][0] = True
 
            for i1 in range(1,n + 1):
              for j in range(1, len(sub) + 1):
                dp[i1][j] = dp[i1 -1][j] or (s[i1 -1] == sub[j -1] and dp[i1 -1][j -1])
 
 
            if dp[n][len(sub)]:
                count +=1
 
        return count
 
    def backtrack(index, current):
        nonlocal best
        if count_subsequence(current) >=k:
            if len(current) > len(best) or (len(current) == len(best) and current > best):
                best = current
        
        for i in range(index, n):
            backtrack(i + 1, current + s[i])
    
    backtrack(0, "")
    return best

Time Complexity Analysis:

The time complexity is dominated by the backtracking algorithm and the subsequence counting. In the worst case, the backtracking explores all possible subsequences, which is O(2n), where n is the length of the string. The subsequence counting using dynamic programming has a complexity of O(n * m), where m is the length of the subsequence. The overall time complexity is approximately O(2n * n * m). However, in practice, the algorithm often performs much faster because many subsequences are pruned early due to the repetition check.

Space Complexity Analysis:

The space complexity is dominated by the dynamic programming table used for subsequence counting, which is O(n * m), and the call stack of the backtracking function, which can be up to O(n) in the worst case. Therefore, the overall space complexity is O(n * m).

Note: The provided Python code showcases the core logic. Optimizations are possible, particularly in the subsequence counting part, to further improve performance. Adapting this approach to other languages (Java, C++, Go) involves straightforward translation of the algorithms and data structures.