2014. Longest Subsequence Repeated k Times
Problem
Given a string s
and an integer k
, you need to find the longest subsequence in the string such that the subsequence is repeated k
times. The characters in the subsequence are selected conservatively(function in program). If there are multiple such subsequences, you need to return the lexicographically largest one. If the answer is empty, return an empty string.
You can think of it as finding out the maximum-length string which could be a repeated subsequence.
Example
Input: s = "abcacb", k = 2 Output: "ab" Explanation: The longest subsequence that occurs at least 2 times is "ab".
Approach
The solution for this problem involves using a BFS (Breadth-First Search) algorithm, along with a queue-based data structure. The solution uses a function isSubsequence
that returns true if the given subsequence is a subsequence of the string for k
times and false otherwise. The algorithm first keeps track of the count of each character in the string, a possible character set, and initials an empty queue with an empty string. Then, it dequeues a subsequence from the queue, and if its length times k is greater than the length of the string, it returns the answer. Otherwise, it iterates over the possible characters, forms new subsequences, and adds them to the queue if they are subsequences of the string. Finally, the answer is returned.
Example
Using the input example s = "abcacb", k = 2
, the algorithm works as follows:
- Count each character's frequency in the string: a:2, b:2, c:2
- Create a list of possible characters: ['a', 'b', 'c']
- Initialize the queue with an empty string: [""]
- Iterate through the BFS queue, forming new subsequences ("a", "ab", "ac", "abc", "acb", "b", "ba", "bc", "bc", "bca", "ca", "cac", "cab", "c", "c").
- While iterating over the new subsequences, add them to the BFS queue if they're subsequences of the string. For example, "ab" is a subsequence of the string, so it's added to the queue: ["", "a", "ab", "ac", "abc", "acb", "b", "ba", "bc", "bc", "bca", "ca", "cac", "cab", "c", "c"].
- Return the largest lexicographically-valid subsequence, which is "ab" in this example.
Algorithm Steps
- Initialize a count array to store the frequency of each character in the string.
- Initialize a possible Characters list that contains characters occurring k times in the string.
- Initialize a BFS queue with an empty string.
- While the queue is not empty:
- Dequeue one subsequence from the queue.
- If the length of the subsequence times k is greater than the length of the string, return the answer.
- Iterate through the possible characters list, form new subsequences, and add them to the queue if they're subsequences of the string.
Solution
Python
python from collections import deque from typing import List class Solution: def longestSubsequenceRepeatedK(self, s: str, k: int) -> str: def is_subsequence(subseq: str, s: str, k: int) -> bool: i = 0 for c in s: if c == subseq[i]: i += 1 if i == len(subseq): k -= 1 if k == 0: return True i = 0 return False count = [0] * 26 possible_chars = [] bfs_queue = deque([""]) for c in s: count[ord(c) - ord('a')] += 1 for c in range(26): if count[c] >= k: possible_chars.append(chr(ord('a') + c)) ans = "" while bfs_queue: curr_subseq = bfs_queue.popleft() if len(curr_subseq) * k > len(s): return ans for c in possible_chars: new_subseq = curr_subseq + c if is_subsequence(new_subseq, s, k): bfs_queue.append(new_subseq) ans = new_subseq return ans
Java
java import java.util.*; class Solution { public String longestSubsequenceRepeatedK(String s, int k) { int[] count = new int[26]; List<Character> possibleChars = new ArrayList<>(); Queue<String> q = new LinkedList<>(Collections.singletonList("")); for (char c : s.toCharArray()) { count[c - 'a']++; } for (char c = 'a'; c <= 'z'; c++) { if (count[c - 'a'] >= k) { possibleChars.add(c); } } String ans = ""; while (!q.isEmpty()) { String currSubseq = q.poll(); if (currSubseq.length() * k > s.length()) { return ans; } for (char c : possibleChars) { String newSubseq = currSubseq + c; if (isSubsequence(newSubseq, s, k)) { q.offer(newSubseq); ans = newSubseq; } } } return ans; } private boolean isSubsequence(String subseq, String s, int k) { int i = 0; for (char c : s.toCharArray()) { if (c == subseq.charAt(i)) { i++; if (i == subseq.length()) { k--; if (k == 0) { return true; } i = 0; } } } return false; } }
JavaScript
javascript class Solution { longestSubsequenceRepeatedK(s, k) { const count = new Array(26).fill(0); const possibleChars = []; const q = [""]; let ans = ""; for (const c of s) { count[c.charCodeAt(0) - "a".charCodeAt(0)]++; } for (let i = 0; i < 26; i++) { if (count[i] >= k) { possibleChars.push(String.fromCharCode("a".charCodeAt(0) + i)); } } while (q.length > 0) { const currSubseq = q.shift(); if (currSubseq.length * k > s.length) { return ans; } for (const c of possibleChars) { const newSubseq = currSubseq + c; if (this.isSubsequence(newSubseq, s, k)) { q.push(newSubseq); ans = newSubseq; } } } return ans; } isSubsequence(subseq, s, k) { let i = 0; for (const c of s) { if (c === subseq[i]) { i++; if (i === subseq.length) { k--; if (k === 0) { return true; } i = 0; } } } return false; } }
C++
cpp
#include <iostream>
#include <queue>
#include <string>
#include <vector>
class Solution {
public:
std::string longestSubsequenceRepeatedK(const std::string& s, int k) {
std::string ans;
std::vector<int> count(26);
std::vector<char> possibleChars;
std::queue<std::string> q{{""}};
for (const char c : s)
++count[c - 'a'];
for (char c = 'a'; c <= 'z'; ++c)
if (count[c - 'a'] >= k)
possibleChars.push_back(c);
while (!q.empty()) {
const std::string currSubseq = q.front();
q.pop();
if (currSubseq.length() * k > s.length())
return ans;
for (const char c : possibleChars) {
const std::string& newSubseq = currSubseq + c;
if (isSubsequence(newSubseq, s, k)) {
q.push(newSubseq);
ans = newSubseq;
}
}
}
return ans;
}
private:
bool isSubsequence(const std::string& subseq, const std::string& s, int k) {
int i = 0;
for (const char c : s)
if (c == subseq[i])
if (++i == subseq.length()) {
if (--k == 0)
return true;
i = 0;
}
return false;
}
};
C#
csharp using System; using System.Collections.Generic; public class Solution { public string LongestSubsequenceRepeatedK(string s, int k) { int[] count = new int[26]; List<char> possibleChars = new List<char>(); Queue<string> q = new Queue<string>(); q.Enqueue(""); string ans = ""; foreach (char c in s) { count[c - 'a']++; } for (char c = 'a'; c <= 'z'; c++) { if (count[c - 'a'] >= k) { possibleChars.Add(c); } } while (q.Count > 0) { string currSubseq = q.Dequeue(); if (currSubseq.Length * k > s.Length) { return ans; } foreach (char c in possibleChars) { string newSubseq = currSubseq + c; if (IsSubsequence(newSubseq, s, k)) { q.Enqueue(newSubseq); ans = newSubseq; } } } return ans; } private bool IsSubsequence(string subseq, string s, int k) { int i = 0; foreach (char c in s) { if (c == subseq[i]) { i++; if (i == subseq.Length) { k--; if (k == 0) { return true; } i = 0; } } } return false; } }
Conclusion
In this article, we have explored the problem of finding the longest repeated subsequence of a string with given k
times. We have provided algorithm steps to solve the problem using a BFS approach and shared the full solution in Python, Java, JavaScript, C++, and C#.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorHow many ways can you arrange the three letters A, B and C?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!