Daily Dose of DSA - Day 14

//Question link : https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
//In this approach we wrote a helper function for m distinct elements and called the helper function 26 times for distinct 26 letters in English alphabet 
class Solution
{
public:
    int helper(string &s, int m, int k)
    {
        int n = (int)s.size();
        int low = 0, high = 0;
        int ans = 0;

        int cc = 0; // number of elements having freq >= k between [low.......high]
        unordered_map<char, int> mp; //for storing the frequency of characters

        while (high < n && low <= high) //window sliding pointers
        {
            mp[s[high]]++;  
            if (mp[s[high]] == k) //we will keep track of the elements which have frequency >=k
                cc++; 

            if ((int)mp.size() == m && cc == m) //case when number of distinct elements becomes m which have frequency >=k
            {
                ans = max(ans, high - low + 1); //as we have to find the longest substring we will keep updating the ans
                high++;
                continue; //continue the iteration
            }

            if ((int)mp.size() <= m && cc < m)
            {
                high++; 
                continue;
            }
/*case in which number of distinct elements become greater than m ,we will decrease the frequency of the element at low pointer and check the conditions for cc , if that element has 0 frequency we will erase that element from the map and we will increment the low pointer */
            while (low <= high && (int)mp.size() > m) 
           {
                mp[s[low]]--;
                if (mp[s[low]] == k - 1)
                    cc--;
                if (mp[s[low]] == 0)
                    mp.erase(s[low]);
                low++;
            }
            high++;
        }
        return ans;
    }
  /*Finally, the function longestSubstring uses a loop to try all possible values of m from 1 to 26 (since there are only 26 distinct lowercase English letters). For each value of m, it calls helper with the current value of m*/
    int longestSubstring(string s, int k)
    {
        int n = (int)s.size();
        int ans = 0;
        for (int i = 1; i <= 26; i++)
        {
            ans = max(ans, helper(s, i, k));
        }
        return ans;

    }
};