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:
Map all characters in string s to a Hash map and store the count of characters as values.
if all characters occur more than k times, then return the whole string length as result;
if not, find the least occured character and split the string by this char, then call this function recursively
to get the max length out of all substrings.
return the max.
public class Solution {
public int LongestSubstring(string s, int k) {
Dictionary<char,int> map = new Dictionary<char, int>();
if(string.IsNullOrEmpty(s))
{
return ;
}
int l = s.Length;
for(int i=; i<l; i++)
{
if(map.ContainsKey(s[i]))
{
map[s[i]]++;
}
else
{
map.Add(s[i],);
}
}
char minKey=map.Aggregate((p, r) => p.Value < r.Value ? p : r).Key;
if(map[minKey]>=k)
{
return l;
}
string[] splitted = s.Split(minKey);
int max = ;
foreach(string n in splitted)
{
int m = LongestSubstring(n,k);
if(m>max)
{
max = m;
}
}
return max;
}
}