13. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:
Input:
s = "aaabb", k = 3

Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:
Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Solution: (Brute Force)

class Solution
{
public:
    bool countChar(vector<int> v, int k)
    {

        for (int i = 0; i < 26; i++)
        {
            if (v[i] != 0)
            {
                if (v[i] < k)
                {
                    return false;
                }
            }
        }
        return true;
    }

    int longestSubstring(string s, int k)
    {

        if (k > s.length())
        {
            return 0;
        }
        if (s == "")
        {
            return 0;
        }

        int maxLen = 0;
        for (int i = 0; i < s.length(); i++)
        {
            vector<int> v(26, 0);
            int j;
            for (j = i; j < s.length(); j++)
            {
                v[s[j] - 97]++;
                if (countChar(v, k))
                {

                    if ((j - i) + 1 > maxLen)
                    {
                        maxLen = (j - i) + 1;
                    }
                }
            }
        }
        return maxLen;
    }
};

Time Complexity: O(n^2)

Solution : (Divide And Conquer)

class Solution
{
public:
    int maxLen(string s, int start, int end, int k)
    {
        vector<int> v(26, 0);
        for (int i = start; i <= end; i++)
        {
            v[s[i] - 97]++;
        }

        int maxL = 0, maxR = 0;
        for (int i = start; i <= end; i++)
        {
            if (v[s[i]-97]!=0 && v[s[i]-97] < k)
            {
                maxL = maxLen(s, start, i - 1, k);
                maxR = maxLen(s, i + 1, end, k);
                return max(maxL, maxR);
            }
        }
        return end - start;
    }

    int longestSubstring(string s, int k)
    {
        return maxLen(s, 0, s.length() - 1, k)+1;
    }
};

Time Complexity: O(N log N)