[Leetcode] 2014. Longest Subsequence Repeated k Times (retry time complexity)

https://leetcode.com/problems/longest-subsequence-repeated-k-times/description/?envType=daily-question&envId=2025-06-27

initial

i was thinking greedily like splitting the longest possible equal subsequence length like half, one third, a quarter. Then check from z to a the available character in our Counter. But there is a problem like when "bbabbabbbbabaababab", k=3, my answer gives "bbab" cuz im taking greedily if the freq of the character is available. But right answer is "bbbb" so we cannot take greedily.

from collections import Counter
class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        counter = Counter(s)
        ans=0
        length=len(s)//k
        for i in range(length,0,-1):
            counter_tmp= counter.copy()
            count=0
            tmp=""
            for j in range(i):
                for z in range(26,-1,-1):
                    if s[j]==chr(z+ord('a')) and counter_tmp[s[j]]//k:
                        tmp+=s[j]
                        count+=1
                        counter_tmp[s[j]]-=1
                        break
            check=0
            for x in range(length,0,-1):
                for a in range(0, len(s),x):
                    if tmp in s[a:a+x]:
                        check+=1
                if check==k:
                    return tmp
        return ""

sol

actually theres a clever trick to check k subsequences in original string.

https://velog.io/@whitehousechef/Generating-palindrome

u just multiply the subsequences*k and check if they are in the original string via iter()

then it makes things easier. Also we dont sort reverse cuz the last valid case will be the lexicographiically highest string value.

i failed to recognise that we can build our valid cases bottom up . We dont rly have to know how to build the subsequence but as long as the frequency is valid (value//k>0) then those are our valid characters and we can just add them to current iteration. BFS

class Solution:
    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        counter = Counter(s)
        ans=""
        length=len(s)//k
        valid_char=[]
        for key in counter.keys():
            if counter[key]//k:
                valid_char.append(key)
        print(valid_char)
        valid_char.sort()

        def check(s, t): 
            t = iter(t)
            return all(c in t for c in s)

        queue=[]
        queue.append(ans)
        tmp=""
        while queue:
            cur = queue.pop(0)
            for word in valid_char:
                hola= cur+word
                if check(hola*k,s):
                    tmp=hola
                    queue.append(hola)
        return tmp

complexity

very complex to anaylse time
its bfs and it grows by the number of options in valid_char.

at depth 1 (subsequences of length 1), there are up to M candidates.
At depth 2 (subsequences of length 2), there are up to M^2
At depth L (subsequences of length L), there are up to M^L

check() worst case is len(ori)*len(subsequence)

queue: In the worst case, the queue can store all valid subsequences of a certain length. The maximum number of such subsequences could be M ^L Each string in the queue has length up to L.
So, the space complexity for the queue is O(M^L * L)