Longest Subsequence Repeated k Times

Hard

Asked by:

18 views

Topics:

StringsDynamic ProgrammingGreedy Algorithms

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:

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the input string 's' and the value of 'k'? Can 'k' ever be zero or negative?
If there are multiple longest subsequences repeated 'k' times, which one should I return? Is there a specific ordering or tie-breaking criteria?
If no subsequence is repeated 'k' times, what should the function return? Should I return an empty string, null, or something else?
Can the input string 's' contain characters other than lowercase English letters? Are there any restrictions on the character set?
Is it possible for the length of the longest repeated subsequence to be zero? In other words, can an empty string be a valid subsequence that is repeated 'k' times?

Brute Force Solution

Approach

The brute force approach to finding the longest repeating subsequence involves checking every single possible subsequence. We generate all subsequences and verify if a given subsequence appears at least the required number of times. We keep track of the longest subsequence that meets the criteria.

Here's how the algorithm would work step-by-step:

Start by generating all possible subsequences of the given text. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
For each generated subsequence, count how many times it appears in the original text without overlapping.
If a subsequence appears at least the required number of times, we consider it a valid candidate.
Keep track of the longest valid subsequence found so far.
Compare the length of each new valid candidate with the length of the current longest valid subsequence.
If a new valid subsequence is longer than the current longest, replace the current longest with the new subsequence.
After checking all possible subsequences, return the longest valid subsequence that was found.

Code Implementation

def longest_subsequence_repeated_k_times_brute_force(text, k):
    longest_repeating_subsequence = ""

    def generate_subsequences(current_subsequence, index):
        if index == len(text):
            return [current_subsequence]

        # Option 1: Exclude the current character
        subsequences = generate_subsequences(current_subsequence, index + 1)

        # Option 2: Include the current character
        subsequences += generate_subsequences(current_subsequence + text[index], index + 1)
        return subsequences

    all_subsequences = generate_subsequences("", 0)
    
    for subsequence in all_subsequences:
        if not subsequence:
            continue

        # Count how many times the subsequence appears
        count = 0
        start_index = 0
        while start_index < len(text):
            index = find_subsequence(text, subsequence, start_index)
            if index == -1:
                break
            count += 1
            start_index = index + len(subsequence)

        # Check if the subsequence appears at least k times
        if count >= k:
            # Keep track of longest valid subsequence
            if len(subsequence) > len(longest_repeating_subsequence):
                longest_repeating_subsequence = subsequence

    return longest_repeating_subsequence

def find_subsequence(text, subsequence, start_index):
    text_index = start_index
    subsequence_index = 0

    while text_index < len(text) and subsequence_index < len(subsequence):
        if text[text_index] == subsequence[subsequence_index]:
            subsequence_index += 1
        text_index += 1

    # The subsequence was found
    if subsequence_index == len(subsequence):
        return text_index - len(subsequence)
    # The subsequence was not found
    else:
        return -1

# Helper method to remove duplicates from subsequence list (Optional optimization to avoid redundant operations) 
#def remove_duplicates(subsequences):
#    return list(dict.fromkeys(subsequences))

Big(O) Analysis

Time Complexity

O(2^n * n * k) – Generating all possible subsequences of a string of length n takes O(2^n) time, as each character can either be included or excluded. For each subsequence, we need to check how many times it appears in the original string, which involves iterating through the string (O(n)) and subsequence. We need to verify that a subsequence appears at least k times, potentially requiring k iterations (in the worst case, a simplified O(k)). Therefore, the overall time complexity is O(2^n * n * k).

Space Complexity

O(2^N) – The algorithm generates all possible subsequences of the input text. In the worst case, the input text has length N, and the number of possible subsequences is 2^N. Storing all these subsequences requires O(2^N) space. Furthermore, to count the occurrences of each subsequence, additional temporary strings or lists might be created, but the dominant space usage remains with storing the generated subsequences. Therefore, the space complexity is O(2^N).

Optimal Solution

Approach

The trick here is to build the longest repeated subsequence in reverse, starting from the longest possible subsequence. We iteratively try adding characters to the potential subsequence and check if it still appears enough times in the original string. This avoids exploring many unnecessary shorter subsequences.

Here's how the algorithm would work step-by-step:

Start by identifying all the unique characters that appear in the original text.
Create a list of possible subsequences to test, starting with the longest possible one formed by combining all unique characters.
Iteratively shorten or modify subsequences and check if they appear at least 'k' times in the original text.
To check the appearance, scan the original text and try to find matches for your subsequence; increase a counter each time you find a full subsequence.
If any potential subsequence appears 'k' times or more, it is valid. Save that subsequence.
Try shorter subsequences derived from saved subsequences by dropping various characters and running the appearance check again, maintaining the longest that still fulfills the frequency requirement.
Repeat the process until you have tested all possibilities and identified the absolute longest repeated subsequence that satisfies the frequency requirement.

Code Implementation

def longest_subsequence_repeated_k_times(text, k):
    unique_characters = sorted(list(set(text)))
    longest_repeating_subsequence = ""

    # Start with the longest possible subsequence and work backwards
    for length in range(len(unique_characters), 0, -1):
        
        def find_all_subsequences(characters, current_subsequence="", index=0):
            if len(current_subsequence) == length:
                yield current_subsequence
                return
            if index >= len(characters):
                return
            yield from find_all_subsequences(characters, current_subsequence + characters[index], index + 1)
            yield from find_all_subsequences(characters, current_subsequence, index + 1)

        for potential_subsequence in find_all_subsequences(unique_characters):
            
            def check_subsequence_occurrence(subsequence, text, k):
                index_in_text = 0
                subsequence_count = 0
                index_in_subsequence = 0

                while index_in_text < len(text):
                    if text[index_in_text] == subsequence[index_in_subsequence]:
                        index_in_subsequence += 1
                        if index_in_subsequence == len(subsequence):
                            subsequence_count += 1
                            index_in_subsequence = 0
                    index_in_text += 1
                return subsequence_count >= k
            
            #Check if the subsequence occurs at least k times
            if check_subsequence_occurrence(potential_subsequence, text, k):
                longest_repeating_subsequence = potential_subsequence
                
                #If we found a valid subsequence, return it
                return longest_repeating_subsequence

    #If no subsequence is found, return an empty string.
    return longest_repeating_subsequence

Big(O) Analysis

Time Complexity

O(2^m * n * k) – Let n be the length of the input string 'text' and m be the number of unique characters in 'text'. The algorithm starts with a subsequence potentially of length m (formed by all unique chars) and explores its subsequences. The number of possible subsequences to test is bounded by O(2^m) since each unique character can be either present or absent. For each potential subsequence, the algorithm checks if it appears at least k times in 'text'. This appearance checking involves scanning 'text' once for each instance of the subsequence, leading to O(n) work per instance and thus O(n*k) to verify k occurrences. Therefore the total time complexity is O(2^m * n * k).

Space Complexity

O(C) – The space complexity is primarily determined by the size of the list of possible subsequences to test. In the worst case, this list could contain all possible subsequences formed from the unique characters of the original string. If C is the number of unique characters (at most 26 for lowercase English letters), the number of possible subsequences is bounded by 2^C (each character either appears or doesn't). The space to store this list would then be O(2^C), however because the length of each subsequence is at most the number of unique characters (C), the space would be bounded by O(C * 2^C). The storage of the saved subsequence is, at most, the length of the unique characters, resulting in at most O(C). Since C is capped by the number of unique characters of the alphabet and is independent of the input string length N, we can simplify the space complexity to O(C) where C is the number of unique characters.

Edge Cases

Case	How to Handle
Empty string s or k <= 0	Return an empty string if the input string is empty or k is non-positive.
String length is less than k	Return an empty string because no subsequence of length at least 1 can be repeated k times if the string length is less than k.
k is very large such that len(s) / k < 1	Return an empty string if the length of the input string divided by k is less than 1 as no subsequence will be possible.
String contains characters that are not useful for forming the subsequence	The algorithm should only consider characters present at least k times to be considered for subsequences.
The longest subsequence occurs at the beginning of the string	The algorithm should correctly identify the subsequence even if it starts from the beginning of the string.
The string 's' contains duplicate characters that can be part of multiple repeated subsequences	Ensure that the same characters used for forming a repeated subsequence are not used more than once within each repeating instance.
There is no valid subsequence that can be repeated k times.	Return an empty string when no repeated subsequence can be constructed as per the conditions.
Maximum input string size leading to potential memory overflow	Optimize the solution to minimize memory usage, potentially employing techniques like dynamic programming with memoization and pruning search space during the construction of the subsequence.

Empty string s or k <= 0

How to Handle:

Return an empty string if the input string is empty or k is non-positive.

String length is less than k

How to Handle:

Return an empty string because no subsequence of length at least 1 can be repeated k times if the string length is less than k.

k is very large such that len(s) / k < 1

How to Handle:

Return an empty string if the length of the input string divided by k is less than 1 as no subsequence will be possible.

String contains characters that are not useful for forming the subsequence

How to Handle:

The algorithm should only consider characters present at least k times to be considered for subsequences.

The longest subsequence occurs at the beginning of the string

How to Handle:

The algorithm should correctly identify the subsequence even if it starts from the beginning of the string.

The string 's' contains duplicate characters that can be part of multiple repeated subsequences

How to Handle:

Ensure that the same characters used for forming a repeated subsequence are not used more than once within each repeating instance.

There is no valid subsequence that can be repeated k times.

How to Handle:

Return an empty string when no repeated subsequence can be constructed as per the conditions.

Maximum input string size leading to potential memory overflow

How to Handle:

Optimize the solution to minimize memory usage, potentially employing techniques like dynamic programming with memoization and pruning search space during the construction of the subsequence.