Longest Subsequence Repeated k Times
You receive 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 " b a bab c ba " .
Produce the longest subsequence repeated k times in string s . If multiple such subsequences are found, produce the lexicographically largest one. If there is no such subsequence, produce an empty string .
Input: s = "letsimpoldevt", k = 2
Output: "let"
Explanation: In this case, "let" is the longest subsequence that can be repeated 2 times.
Input: s = "bb", k = 2
Output: "b"
Explanation: In this case, the longest subsequence repeated 2 times is "b".
Input: s = "ab", k = 2
Output: ""
Explanation: In this case, there is no subsequence repeated 2 times. Empty string is returned.
Constraints
n == s.length2 <= k <= 20002 <= n < min(2001, k * 8)sconsists of lowercase English letters.
Did this problem appear in one of your interviews?
Responses stay private.