Is Longest Subsequence Repeated k Times easy or hard?

This problem is classified as Hard because it combines subsequence validation with exponential search. Efficient pruning using character frequencies and lexicographic ordering is necessary to keep the candidate exploration manageable.

Longest Subsequence Repeated k Times Python/Java solution

Python and Java implementations typically use backtracking with pruning. The algorithm builds candidate strings, checks whether candidate * k is a subsequence of s, and updates the best result based on length and lexicographic order. The same logic can also be implemented iteratively in C++ or JavaScript.

How to solve Longest Subsequence Repeated k Times in O(n)?

A strict O(n) solution is not possible because the algorithm must explore candidate subsequences. The practical solution reduces the search space using frequency filtering and pruning. After limiting characters to those appearing at least k times, candidate strings are tested using a linear subsequence check over s.

What is the best approach for Longest Subsequence Repeated k Times?

Backtracking with pruning is the most effective strategy. The algorithm builds candidate subsequences using only characters that appear at least k times in the string. Each candidate is validated by checking if it can appear k times as a subsequence of s. Early pruning removes invalid prefixes, keeping the search space manageable.

Is Longest Subsequence Repeated k Times asked at Google/Amazon/Meta?

Problems involving subsequence enumeration, pruning, and greedy ordering frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of backtracking, subsequence validation, and optimization through frequency filtering.

What data structure is used in Longest Subsequence Repeated k Times?

The solution primarily uses a frequency counter (hash map or array) to track character counts and restrict the search alphabet. Backtracking or queue-based enumeration stores candidate subsequences, while a simple pointer scan over the string validates subsequence repetition.

What is the time complexity of Longest Subsequence Repeated k Times?

The complexity is roughly O(26^m * n), where m is the length of the resulting subsequence and n is the length of the input string. Each candidate subsequence is tested by scanning the string once to verify whether it repeats k times. Because characters must appear at least k times, m remains small in practice.

Description Hints 3 Solution Video 48:15

2014. Longest Subsequence Repeated k Times

Hard71.3% acceptance3 companies

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.

Asked at 3 companies

Topics

Hints open one at a time

Hint 1

The length of the longest subsequence does not exceed n/k. Do you know why?

Hint 2

Find the characters that could be included in the potential answer. A character occurring more than or equal to k times can be used in the answer up to (count of the character / k) times.

Hint 3

Try all possible candidates in reverse lexicographic order, and check the string for the subsequence condition.

48:15

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution