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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Subsequence Repeated k Times

Number: 2140

Difficulty: Hard

Paid? No

Companies: Meta

Problem Description

Given a string s and an integer k, find the longest subsequence seq such that seq repeated k times (i.e. seq concatenated with itself k times) is a subsequence of s. If multiple subsequences of maximum length exist, choose the lexicographically largest one. If no subsequence exists that satisfies the requirement, return an empty string.

Key Insights

  • Count the frequency of each character in s; a character is only usable if it appears at least k times.
  • The maximum possible length for the candidate subsequence is bounded by the available counts (each letter can be used at most floor(freq(letter)/k) times).
  • Use backtracking (DFS) to generate candidate subsequences from the available characters, exploring in reverse lexicographical order so that the lexicographically larger valid candidate is found first.
  • For each candidate, verify that the string formed by repeating the candidate k times is a subsequence of s using a two-pointer technique.
  • Pruning is possible by checking if the remaining character counts can still complete a candidate of length equal to the current best or candidate length limits.

Space and Time Complexity

Time Complexity: In the worst-case, the DFS explores O(26^L) candidate subsequences where L is the maximum candidate length (bounded by the frequency counts, and given the constraint n < k * 8, L is small). Each candidate verification takes O(n).
Space Complexity: O(n) for auxiliary space in the subsequence check and O(L) for recursion, which is effectively constant due to small L.

Solution

The solution first precomputes the frequency of each character in s and limits the available characters to those meeting the minimum required frequency (k times). We then use a recursive DFS/backtracking strategy to build candidate subsequences. For each candidate, we form the string by repeating it k times and check if it is a subsequence of s using a two-pointer scan of s. The DFS is performed in descending lexicographical order so that the first valid candidate of the maximum possible length is the answer (both longest and lexicographically largest). Key data structures include frequency count arrays, recursion stack (for DFS), and pointer variables for the subsequence check.

Code Solutions

# Python solution with detailed comments
class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        from collections import Counter
        # Count frequency of each character in s
        char_count = Counter(s)
        # Keep only characters that occur at least k times
        valid_chars = {c: char_count[c] // k for c in char_count if char_count[c] >= k}
        # Candidate letters sorted in reverse order (for lexicographical maximization)
        candidates = sorted(valid_chars.keys(), reverse=True)
        
        best = ""
        
        # Helper function to check if t repeated k times is a subsequence of s
        def is_valid(t: str) -> bool:
            # Form the repeated sequence
            target = t * k
            i = 0  # pointer for s
            for ch in target:
                # Move pointer in s until we find ch
                while i < len(s) and s[i] != ch:
                    i += 1
                if i == len(s):
                    return False
                i += 1
            return True
        
        # DFS/backtracking function to build the candidate subsequence
        def dfs(path: str, counts: dict):
            nonlocal best
            # Check if the current candidate (if non-empty) repeated k times is valid.
            if path and is_valid(path):
                # Update best if path is longer or lexicographically larger if the same length.
                if len(path) > len(best) or (len(path) == len(best) and path > best):
                    best = path
            # Try to add each candidate character in descending lex order.
            for c in candidates:
                # Prune: Ensure we have remaining counts for c
                if counts[c] > 0:
                    counts[c] -= 1
                    # The maximum length obtainable with the current path is limited by available counts.
                    # If even with all remaining characters appended, we cannot exceed best, we can stop.
                    possible_remaining = sum(counts.values())
                    if len(path) + 1 + possible_remaining >= len(best):
                        dfs(path + c, counts)
                    counts[c] += 1  # Backtrack
        
        dfs("", valid_chars.copy())
        return best

# Example usage:
# sol = Solution()
# print(sol.longestSubsequenceRepeatedK("letsleetcode", 2))  # Output: "let"
← Back to All Questions