Longest Subsequence Repeated k Times

Longest Subsequence Repeated k Times

What is this problem about?

This challenging string problem gives you a string s and an integer k. You need to find the longest subsequence sub that, when repeated k times sequentially, is still a valid subsequence of the original string s. If there are multiple subsequences of the same maximum length, you must return the one that is lexicographically largest.

Why is this asked in interviews?

This is a Hard-level problem asked by top-tier companies like Meta and Google. It tests your ability to combine multiple advanced concepts: Frequency Maps, Combinatorics (Enumeration), and String Matching. It evaluates whether you can severely prune a search space, as blindly generating all subsequences of a string of length 10,000 is mathematically impossible.

Algorithmic pattern used

This problem uses Counting/Filtering followed by Breadth-First Search (BFS) / Combinatorics. First, you count the frequencies of all characters in s. Since the subsequence must be repeated k times, any character that appears fewer than k times in s can be completely discarded. You gather the valid characters (each can be used count / k times). Because the resulting string will be very small (maximum length 7 based on problem constraints), you can use BFS to generate all possible combinations of these valid characters, checking if candidate * k is a subsequence of s.

Example explanation

Let s = "letsleetcode", k = 2.

1. Count frequencies: l:2, e:4, t:2, s:1, c:1, o:1, d:1.
2. Keep characters appearing $\ge 2$ times: l (can use 1), e (can use 2), t (can use 1).
3. We generate candidates using BFS, starting from length 1.

• Try "e", "l", "t". Are "ee", "ll", "tt" subsequences of s? Yes.
• Expand to length 2: "el", "te", "le", etc.
• Try "let". let * 2 is "letlet". Is "letlet" a subsequence of "letsleetcode"? Yes!
• "let" length is 3. Since there are no longer valid combinations, "let" is the longest.

Common mistakes candidates make

A common error is trying to apply standard DP (like Longest Common Subsequence) to this problem, which fundamentally fails because the "repeated k times" constraint breaks standard contiguous interval logic. Another mistake is failing to build the candidates in lexicographical order or failing to sort the valid characters properly before starting the BFS, making it difficult to find the "lexicographically largest" answer.

Interview preparation tip

When tackling the Longest Subsequence Repeated k Times interview pattern, leverage the constraints! When the problem implies the final answer will be very short (e.g., length $\le 7$), it is a massive hint that Permutation/BFS is the intended route. Always filter your alphabet first to drastically shrink your search space.