Longest Substring with At Least K Repeating Characters

longest_substring.cpp

class Solution {
public:
    int longestSubstring(string s, int k) {
        vector<int> count = getCharCount(s);
        for (int i = 0; i < count.size(); ++i) {
            char ch = i + 'a';
            
            if (count[i] > 0 && count[i] < k) {
                int max_len = INT_MIN;
                vector<string> splits = splitString(s, ch);
                
                for (const string &ss: splits) {
                    max_len = max(max_len, longestSubstring(ss, k));
                }
                
                return max_len;
            }
        }
        
        return s.length();
    }
    
private:
    vector<int> getCharCount(string s) {
        vector<int> count(26, 0);
        for (char ch: s)
            ++count[ch - 'a'];
        
        return count;
    }
    
    vector<string> splitString(string s, char delim) {
        vector<string> result;
        vector<int> occurences;
        int len = s.length();
        
        for (int i = 0; i < len; ++i)
            if (s[i] == delim)
                occurences.push_back(i);
        occurences.push_back(len);
        
        int start = 0;
        for (int idx: occurences) {
            result.push_back(s.substr(start, idx - start));
            start = idx + 1;
        }
        
        return result;
    }
};