This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
2014. Longest Subsequence Repeated k Times
Difficulty: Hard
Topics: String, Backtracking, Greedy, Counting, Enumeration
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.
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 repeated2times in the string"bababcba", because the string"bbabba", constructed by concatenating"bba"2times, is a subsequence of the string "bababcba".
Return the longest subsequence repeated k times in string s. If multiple such subsequences are found, return the lexicographically largest one. If there is no such subsequence, return an empty string.
Example 1:
- Input: s = "letsleetcode", k = 2
- Output: "let"
- Explanation: There are two longest subsequences repeated 2 times: "let" and "ete". "let" is the lexicographically largest one.
Example 2:
- Input: s = "bb", k = 2
- Output: "b"
- Explanation: The longest subsequence repeated 2 times is "b".
Example 3:
- Input: s = "ab", k = 2
- Output: ""
- Explanation: There is no subsequence repeated 2 times. Empty string is returned.
Constraints:
n == s.length2 <= n, k <= 20002 <= n < k * 8-
sconsists of lowercase English letters.
Hint:
- The length of the longest subsequence does not exceed n/k. Do you know why?
- Find the characters that could be included in the potential answer. A character occurring more than or equal to k times can be used in the answer up to (count of the character / k) times.
- Try all possible candidates in reverse lexicographic order, and check the string for the subsequence condition.
Solution:
We need to find the longest subsequence repeated k times in a given string s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The solution involves generating potential subsequences in descending lexicographical order and checking if they can be repeated k times within s.
Approach
-
Frequency Analysis: First, we count the frequency of each character in the string. Only characters that appear at least
ktimes can be part of the solution. - Valid Characters: We collect characters that meet the frequency requirement and sort them in descending order to prioritize lexicographically larger candidates.
- Depth-First Search (DFS): For each possible subsequence length from the maximum possible (7, as per constraints) down to 1, we generate candidate subsequences in descending lexicographical order. This ensures that the first valid candidate found for a given length is the lexicographically largest.
-
Validation Check: For each candidate subsequence, we check if it can be repeated
ktimes withinsby verifying that the concatenated subsequence appears as a subsequence ins. - Early Termination: The search starts from the longest possible subsequence length. Once a valid candidate is found, it is immediately returned, ensuring efficiency by avoiding unnecessary checks for shorter lengths.
Let's implement this solution in PHP: 2014. Longest Subsequence Repeated k Times
<?php
/**
* @param String $s
* @param Integer $k
* @return String
*/
function longestSubsequenceRepeatedK($s, $k) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* @param $len
* @param $path
* @param $valid
* @param $freq
* @param $k
* @param $s
* @return array|bool|int|int[]|mixed|string|null
*/
private function dfs($len, $path, $valid, $freq, $k, $s) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* @param $s
* @param $seq
* @param $k
* @return bool
*/
private function isKSub($s, $seq, $k) {
...
...
...
/**
* go to ./solution.php
*/
}
// Test cases
echo longestSubsequenceRepeatedK("letsleetcode", 2); // Output: "let"
echo longestSubsequenceRepeatedK("bb", 2); // Output: "b"
echo longestSubsequenceRepeatedK("ab", 2); // Output: ""
?>
Explanation:
-
Frequency Analysis: The code starts by counting the occurrences of each character in the string
sto determine which characters can potentially form the subsequence (those appearing at leastktimes). - Valid Characters: Characters meeting the frequency threshold are collected and sorted in descending order to prioritize lexicographically larger candidates during subsequence generation.
-
DFS for Subsequence Generation: The algorithm uses a depth-first search to generate subsequences of lengths from the maximum possible (7) down to 1. For each length, it builds candidates by appending valid characters to the current path, ensuring character usage does not exceed
floor(frequency / k). -
Validation Check: For each generated candidate, the algorithm checks if the candidate repeated
ktimes forms a valid subsequence insby traversingsand matching characters in order. - Early Termination: The search terminates as soon as the longest valid subsequence is found, ensuring efficiency by leveraging the sorted order of valid characters and descending length prioritization.
This approach efficiently narrows down potential candidates while ensuring optimality by leveraging sorting and early termination strategies.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
MD ARIFUL HAQUE | Sciencx (2025-06-27T05:07:15+00:00) 2014. Longest Subsequence Repeated k Times. Retrieved from https://www.scien.cx/2025/06/27/2014-longest-subsequence-repeated-k-times/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.