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;
}
};