Abstract / Summary

Find the longest sequence that can be repeated k times and appears in the given string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 71% (100k+ submissions).

Typical patterns to solve this problem:

• Backtracking
• Counting
• Enumeration
• Hash Table
• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation defines a class Solution with a single method longestSubsequenceRepeatedK. The method receives a string s and an integer k, and returns the longest subsequence that can be repeated exactly k times as a subsequence of s. If several subsequences share the maximum length, the lexicographically largest one is chosen. The algorithm proceeds in three logical phases: frequency counting, candidate preparation, and iterative construction of repeated subsequences.

Frequency Counting

The first phase builds a histogram of character occurrences using a defaultdict. This structure provides constant-time updates and avoids explicit existence checks.

freq = defaultdict(int)
for c in s:
    freq[c] += 1

By iterating over the input once, the code gathers the exact count of each character, which later determines which characters are eligible for inclusion in any repeated subsequence.

Candidate Preparation

Only characters that appear at least k times can possibly belong to a subsequence that repeats k times. The code filters the original string accordingly, preserving the original order of appearance, and then extracts the distinct set of such characters, sorted to impose a deterministic order.

active = [c for c in s if freq[c] >= k]
add = sorted(set(active))

active serves as the search space for the subsequence test, while add supplies the alphabet of letters that may be appended during the construction phase. By discarding low-frequency characters early, the algorithm reduces the branching factor of the subsequent search.

Iterative Construction

The core of the algorithm is a breadth-first expansion of candidate patterns. It starts with the empty string and repeatedly attempts to extend each current pattern by every character in add. For each extension, the code builds the candidate pattern pattern and the target repeated string search, which is simply pattern concatenated k times.

todo = [""]
while todo:
    next = []
    for t in todo:
        for a in add:
            pattern = t + a
            search = pattern * k
            # subsequence verification follows

Subsequence Verification

The verification step checks whether search appears as a subsequence of active. A pointer pos tracks progress through search. As the loop scans active, each matching character advances pos. The loop terminates early as soon as the entire search has been matched.

pos = 0
for c in active:
    if c == search[pos]:
        pos += 1
        if pos == len(search):
            break

If the pointer reaches the end of search, the current pattern is a valid repeated subsequence. The algorithm records it as the current best result and queues it for further extension in the next iteration.

if pos == len(search):
    result = pattern
    next.append(pattern)

The outer while loop continues until no further extensions succeed, at which point todo becomes empty and the most recent result holds the longest (and lexicographically largest) repeated subsequence.

Edge Cases Handled

When the input string is empty, the frequency map remains empty, active and add become empty lists, and the loop terminates immediately, returning the initial empty string.

If k exceeds the total length of s, no character can satisfy the frequency condition, leading again to an empty add and an immediate exit with an empty result.

When multiple characters meet the frequency threshold but no combination can be repeated k times, the algorithm explores all single-character extensions, fails to find a match, and ultimately returns an empty string.

The early break in the subsequence scan ensures that even very long search strings are processed efficiently when a match is found early in active.

Because add is sorted, extensions are examined in lexical order; however, the assignment result = pattern overwrites previous candidates, so the final value corresponds to the last successful pattern in the iteration order, which aligns with the requirement for the lexicographically largest among equally long candidates.

Performance Optimizations

The use of a frequency filter eliminates characters that could never contribute to a valid answer, dramatically shrinking the search space for large inputs with many low-frequency symbols.

Storing active preserves the original ordering of characters that matter, allowing the subsequence check to run in a single linear pass without auxiliary data structures.

The subsequence verification loop stops as soon as the full search is matched, avoiding unnecessary scans of the remainder of active.

By constructing search as a repeated concatenation of pattern (pattern * k), the algorithm avoids repeated string multiplication inside the inner loop, keeping the per-extension cost low.

The breadth-first expansion ensures that once a pattern fails to extend, all its longer descendants are automatically pruned, preventing exponential blow-up in practice for typical inputs.

Overall, the combination of frequency pruning, ordered candidate generation, and early termination in the subsequence check yields a solution that scales well with the size of the input string while respecting the constraints imposed by k.

Imagine you have a big bucket full of colorful letter blocks. You want to make a special train out of these blocks, but there is a rule. Every color in your train must appear at least as many times as the number k in your big bucket.

First, look through the bucket and throw away any letter that does not show up enough times. Those letters are just noise and will not help build the train. Now you are left with only the good, useful letters.

Start by picking one letter to begin the train. Check if that letter appears enough times in the pile to fulfill the requirement. If it does, keep it and try adding another letter to make the train a little bit longer. Every time a new train pattern is found that meets the rule, save it. Then, try adding yet another letter to see if that works too. Keep growing the train as long as possible, always checking that enough of those letters exist in the pile to match the repetition rule. This process continues until no more letters can be added to make a valid train. The very last train made this way is the longest one found.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python	TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java		Go	Python	TS
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	suxrobGM				C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality