2014. Longest Subsequence Repeated k Times
Approach
BFS over candidate subsequences in increasing length order. Only characters
appearing ≥ k times in s can appear in the answer. For each candidate, greedily verify
if it appears as a subsequence k times in s. Track the longest valid candidate found.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Backtracking explores all possible solutions by building candidates incrementally and abandoning ("pruning") branches that cannot lead to a valid result. It powers N-Queens, Sudoku solver, permutations, and subset generation. Prune early to reduce the effective search space.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
// Approach: BFS over candidate subsequences in increasing length order. Only characters
// appearing ≥ k times in s can appear in the answer. For each candidate, greedily verify
// if it appears as a subsequence k times in s. Track the longest valid candidate found.
// Time: O(n * |candidates|) Space: O(|candidates|)
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>(new[] { "" });
foreach (char c in s)
count[c - 'a']++;
for (char c = 'a'; c <= 'z'; c++)
{
if (count[c - 'a'] >= k)
possibleChars.Add(c);
}
string ans = "";
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;
}
}