Longest Subsequence Repeated k Times | Leetcode 2014

class Solution {
    int countSubsequences(const string& s,const string& next){
        int i=0;//Index in s
        int j=0;//Index in next
        int m = next.size();
        int subsequence_count = 0;

        while(i<s.size()){
            if(s[i]==next[j]){
                j++;
                if(j==m){
                    j=0;
                    subsequence_count++;
                }
            }
            i++;
        }
        return subsequence_count;
    }
public:
    string longestSubsequenceRepeatedK(string s, int k) {
        int n=s.size();
        vector<int> freq(26);
        for(int i=0;i<n;++i)
            freq[s[i]-'a']++;
        
        //BFS
        string curr = "";
        queue<string> q;
        q.push(curr);
        string res;

        while(!q.empty()){
            curr = q.front();
            q.pop();
            
            string next = curr;
            for(char c='a';c<='z';++c){//Runs for maximum 7 chars
                if(freq[c-'a']<k)
                    continue;
                next.push_back(c);
                if(countSubsequences(s,next)>=k){
                    res = next;
                    q.push(next);
                }
                next.pop_back();
            }
        }
        return res;
    }
};
/*
//JAVA
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    private int countSubsequences(String s, String next) {
        int i = 0; // Index in s
        int j = 0; // Index in next
        int m = next.length();
        int subsequenceCount = 0;

        while (i < s.length()) {
            if (s.charAt(i) == next.charAt(j)) {
                j++;
                if (j == m) {
                    j = 0;
                    subsequenceCount++;
                }
            }
            i++;
        }
        return subsequenceCount;
    }

    public String longestSubsequenceRepeatedK(String s, int k) {
        int n = s.length();
        int[] freq = new int[26];
        for (int i = 0; i < n; ++i) {
            freq[s.charAt(i) - 'a']++;
        }

        // BFS
        String curr = "";
        Queue<String> queue = new LinkedList<>();
        queue.offer(curr);
        String res = "";

        while (!queue.isEmpty()) {
            curr = queue.poll();
            
            for (char c = 'a'; c <= 'z'; ++c) {
                if (freq[c - 'a'] < k) {
                    continue;
                }
                String next = curr + c;
                if (countSubsequences(s, next) >= k) {
                    res = next;
                    queue.offer(next);
                }
            }
        }
        return res;
    }
}

#Python
from collections import deque

class Solution:
    def countSubsequences(self, s: str, next_str: str) -> int:
        i = 0  # Index in s
        j = 0  # Index in next_str
        m = len(next_str)
        subsequence_count = 0

        while i < len(s):
            if s[i] == next_str[j]:
                j += 1
                if j == m:
                    j = 0
                    subsequence_count += 1
            i += 1
        return subsequence_count

    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:
        n = len(s)
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1

        # BFS
        curr = ""
        queue = deque()
        queue.append(curr)
        res = ""

        while queue:
            curr = queue.popleft()
            
            for c in range(ord('a'), ord('z') + 1):
                char = chr(c)
                if freq[c - ord('a')] < k:
                    continue
                next_str = curr + char
                if self.countSubsequences(s, next_str) >= k:
                    res = next_str
                    queue.append(next_str)
        return res
*/