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.
// 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;
    }
}