LeetCode Daily Challenge-2014. Longest Subsequence Repeated k Times(Hard)

• LeetCode Link
• Topics: String,Backtracking,Greedy,Counting,Enumeration,DFS
• Date: 27th June 2025

Problem Statement

Given a string s and an integer k, return the longest subsequence of s such that the subsequence can be repeated k times as a subsequence of s. A subsequence can be derived from another string by deleting some or no elements without changing the order of the remaining elements.

Understanding the Problem

This problem has two key requirements:

1. Find a subsequence from the original string s
2. This subsequence, when repeated k times, must still be a valid subsequence of s

For example, if s = "letsleetcode" and k = 2, we need to find the longest subsequence that appears at least twice in s without overlapping positions.

The DFS Strategy

The solution uses a depth-first search (DFS) approach combined with several key optimizations:

1. Character Frequency Filtering

Only characters that appear at least k times in the original string can be part of our answer. This is because if a character appears fewer than k times, it cannot be part of a subsequence that repeats k times.

2. Lexicographic Ordering

We process candidate characters in reverse lexicographic order. This ensures that when we find subsequences of the same length, we naturally prefer the lexicographically larger one.

3. Iterator-Based Validation

The validation function uses Python's iterator approach to efficiently check if a subsequence can be formed from the original string.

Code Walkthrough

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        ans = ""

        # Step 1: Filter characters that appear at least k times
        # Sort in reverse order for lexicographic preference
        candidate = sorted(
            [c for c, w in Counter(s).items() if w >= k], 
            reverse=True
        )

        def is_valid_subsequence(subseq):
            """Check if subsequence can be repeated k times using iterator approach"""
            it = iter(s)
            return all(ch in it for ch in subseq * k)

        def dfs(current_subseq):
            nonlocal ans

            # Update answer if current subsequence is better
            if len(current_subseq) > len(ans):
                ans = current_subseq
            elif len(current_subseq) == len(ans) and current_subseq > ans:
                ans = current_subseq

            # Try extending with each candidate character
            for ch in candidate:
                next_subseq = current_subseq + ch

                # Only continue DFS if the new subsequence is valid
                if is_valid_subsequence(next_subseq):
                    dfs(next_subseq)

        # Start DFS from empty string
        dfs("")
        return ans

Deep Dive: The Validation Function

The is_valid_subsequence function is the heart of the solution:

def is_valid_subsequence(subseq):
    it = iter(s)
    return all(ch in it for ch in subseq * k)

This elegant one-liner works by:

1. Creating an iterator over the original string s
2. For each character in the repeated subsequence (subseq * k), checking if it can be found in the remaining part of the string
3. The in operator automatically advances the iterator, ensuring we don't reuse characters

Example of Iterator Behavior

For s = "letsleetcode", subseq = "le", k = 2:

• We need to check if "lele" can be formed as a subsequence
• Iterator starts at position 0: l|etsleetcode
• Find 'l' at position 0, iterator advances: l|etsleetcode
• Find 'e' at position 1, iterator advances: le|tsleetcode
• Find 'l' at position 4, iterator advances: lets|eetcode
• Find 'e' at position 5, iterator advances: letsle|etcode
• All characters found successfully!

DFS Exploration Strategy

The DFS systematically explores all possible subsequences:

1. Base Case: Update the answer if the current subsequence is better (longer or lexicographically larger)
2. Recursive Case: Try appending each candidate character and recursively explore if the resulting subsequence is valid
3. Pruning: Only continue DFS if the current subsequence can actually be repeated k times

Step-by-Step Execution

Let's trace through s = "letsleetcode", k = 2:

1. Character Frequency Count:

   • 'l': 2, 'e': 4, 't': 2, 's': 1, 'c': 1, 'o': 1, 'd': 1
   • Valid candidates: ['l', 'e', 't'] (appear ≥ 2 times)
   • Sorted reverse: ['t', 'l', 'e']

2. DFS Exploration:

   • Start with ""
   • Try "t": Check if "tt" is valid subsequence → Valid, continue DFS
   • Try "tl": Check if "tltl" is valid subsequence → Invalid, backtrack
   • Try "te": Check if "tete" is valid subsequence → Valid, continue DFS
   • And so on...

3. Final Answer: The longest valid subsequence might be "ete" or similar

Time and Space Complexity

• Time Complexity: O(2^c × n × k) where c is the number of candidate characters and n is the length of the string. In the worst case, we explore all possible subsequences.
• Space Complexity: O(c × max_length) for the recursion stack, where max_length is the length of the longest valid subsequence.

Key Optimizations

1. Character Filtering

By only considering characters that appear at least k times, we dramatically reduce the search space.

2. Lexicographic Ordering

Processing characters in reverse order ensures we find the lexicographically largest answer when multiple answers have the same length.

3. Early Termination

The validation function fails fast when a subsequence cannot be repeated k times.

4. Iterator Efficiency

Using Python's iterator pattern makes the subsequence validation both elegant and efficient.

Edge Cases to Consider

• When k = 1: Any subsequence of s is valid
• When no character appears k times: Return empty string
• When s has length less than k: Maximum possible answer length is very limited
• When all characters are the same: Answer is the character repeated as many times as possible

Alternative Approaches

While this DFS solution is intuitive, other approaches could include:

• BFS: Explore subsequences level by level
• Dynamic Programming: Build up solutions using previously computed results
• Greedy with Backtracking: Try to build the lexicographically largest solution first

The DFS approach strikes a good balance between clarity and efficiency, making it an excellent choice for this problem's constraints.

Conclusion

This problem beautifully combines string manipulation, subsequence validation, and search algorithms. The key insight is recognizing that only frequently occurring characters can be part of the solution, which dramatically reduces the search space. The iterator-based validation provides an elegant way to check if a subsequence can be repeated k times, making this solution both efficient and readable.