Longest_Substring.png
int longestSubstring(char * s, int k){
int len = 0, n = strlen(s);
if (k == 1) return n;
int first[26], start[n], num[26];
for (int i = 0; i < 26; i++) {
num[i] = 0;
first[i] = -1;
}
for (int i = 0; i < n; i++) { start[i] = i; }
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
if (first[c] == -1) { first[c] = i; }
num[c]++;
if (num[c] >= k) {
int j = i - 1, left = first[c], min[26];
for (int ic = 0; ic < 26; ic++) { min[ic] = 0; }
min[c] = 1;
while (j >= left && num[s[j] - 'a'] >= k) {
min[s[j] - 'a']++;
if (start[j] != j) {
j = start[j];
} else {
j--;
}
if (j >= 0 && num[s[j] - 'a'] >= k && left > first[s[j] - 'a']) { left = first[s[j] - 'a']; }
}
if (j == left - 1) {
int tlen = i - j;
if (len < tlen) { len = tlen; }
} else {
int mink = n;
for (int ic = 0; ic < 26; ic++) { if (min[ic] != 0 && min[ic] < mink) { mink = min[ic]; } }
if (mink < n && mink >= k) {
int tlen = i - j;
if (len < tlen) { len = tlen; }
}
}
}
}
return len;
}
