2014. Longest Subsequence Repeated k Times

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 repeated 2 times in the string “bababcba”, because the string “bbabba”, constructed by concatenating “bba” 2 times, 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.

class Solution {
public:
    string longestSubsequenceRepeatedK(string s, int k) {
        queue<string> q;
        string res = "";
        q.push(res);
        while(!q.empty()) {
            auto sub = q.front(); q.pop();
            for(int i = 0; i < 26; i++) {
                string nsub = sub + string(1, 'a' + i);
                if(nsub.length() * k <= s.length()) {
                    if(isSub(s,nsub,k)) {
                        q.push(nsub);
                        res = nsub;
                    }
                }
            }
        }
        return res;
    }
    bool isSub(string& o, string& sub, int k) {
        for(int i = 0, j = 0; i < o.length() and k; i++) {
            if(o[i] == sub[j]) {
                j = (j + 1) % sub.length();
                if(!j) k--;
            }
        }
        return k == 0;
    }
};