We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Subsequence Repeated k Times

Difficulty: Hard

Problem Description

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. 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.

Key Insights

  • A subsequence can include any characters from the original string as long as their order is maintained.
  • We need to construct a candidate subsequence and check if it can be repeated k times within the original string.
  • The lexicographical order is important when multiple longest subsequences exist.
  • The problem can be approached using a backtracking or greedy algorithm to generate potential subsequences.

Space and Time Complexity

Time Complexity: O(n^k) in the worst case for generating subsequences, but practical optimizations will reduce this significantly. Space Complexity: O(n) for storing subsequences and any auxiliary data structures used during the algorithm.

Solution

The approach involves generating subsequences of the original string and checking each subsequence to see if it can be repeated k times. We can utilize a recursive backtracking algorithm to explore all possible subsequences in a structured way. For each valid subsequence, we verify if it can be constructed k times by traversing the original string. The longest valid subsequence will be stored and compared lexicographically to ensure the correct output.

Code Solutions

def longestSubsequenceRepeatedK(s: str, k: int) -> str:
    from collections import Counter

    # Count frequency of each character in the string
    freq = Counter(s)
    
    # Create a list of characters sorted in reverse order (for lexicographical order)
    sorted_chars = sorted(freq.keys(), reverse=True)
    result = []
    
    # Attempt to create the longest subsequence
    for char in sorted_chars:
        # Check how many times we can add this character to the result
        while freq[char] >= k:
            result.append(char)
            freq[char] -= k
            
    # Construct the longest subsequence
    return ''.join(result)
← Back to All Questions