How hard is LeetCode 2014. Longest Subsequence Repeated k Times?

LeetCode 2014. Longest Subsequence Repeated k Times is rated Hard on LeetCode.

What topics does LeetCode 2014. Longest Subsequence Repeated k Times cover?

LeetCode 2014. Longest Subsequence Repeated k Times is tagged Greedy, String, Backtracking, Counting and Enumeration on LeetCode.

Longest Subsequence Repeated k Times — LeetCode 2014 Python Solution

HardGreedyStringBacktrackingCountingEnumeration

Problem: #2014
Pattern: Backtracking
Reading time: 5 min
Source: leetcode.com

The problem

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.

Example

Input: s = "letsleetcode", k = 2
Output: "let"
Explanation: There are two longest subsequences repeated 2 times: "let" and "ete".

Python solution

Python

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        def check(t: str, k: int) -> bool:
            i = 0
            for c in s:
                if c == t[i]:
                    i += 1
                    if i == len(t):
                        k -= 1
                        if k == 0:
                            return True
                        i = 0
            return False

        cnt = Counter(s)
        cs = [c for c in ascii_lowercase if cnt[c] >= k]
        q = deque([""])
        ans = ""
        while q:
            cur = q.popleft()
            for c in cs:
                nxt = cur + c
                if check(nxt, k):
                    ans = nxt
                    q.append(nxt)
        return ans

Complexity

Measure	Complexity
Time	O(n log n)
Space	O(1) to O(n) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2014. Longest Subsequence Repeated k Times is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2014. Longest Subsequence Repeated k Times?: LeetCode 2014. Longest Subsequence Repeated k Times is rated Hard on LeetCode.
What topics does LeetCode 2014. Longest Subsequence Repeated k Times cover?: LeetCode 2014. Longest Subsequence Repeated k Times is tagged Greedy, String, Backtracking, Counting and Enumeration on LeetCode.