HardNo. 2014
Longest Subsequence Repeated k Times — LeetCode 2014 Python Solution
- Pattern
- Backtracking
- Topics
- Greedy, String, Backtracking, Counting, Enumeration
- 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
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 ansComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1221 | Split a String in Balanced Strings | Easy |
| 2259 | Remove Digit From Number to Maximize Result | Easy |
| 2375 | Construct Smallest Number From DI String | Medium |
| 2800 | Shortest String That Contains Three Strings | Medium |
| 2844 | Minimum Operations to Make a Special Number | Medium |
| 0179 | Largest Number | Medium |
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.