Store locations of the elements and a frequency map of characters per index. At each index try to see if removing all the characters occurring less than k times results in a correct substring.

```
def longestSubstring(self, s, k):
positions = [ [-1] for _ in range(ord('a'), ord('z')+1) ]
for i,v in enumerate(s):
positions[ord(v)-ord('a')].append(i)
def checkCorrect(dic, index):
i = 0
zero = 0
while i<len(dic):
if dic[i]<k:
poss = positions[i]
zero = max(zero,poss[ dic[i] ]+1)
i+=1
if zero != 0:
dic2 = dicCollection[zero-1]
for i,v in enumerate(dic):
if 0<v-dic2[i]<k:
return 0
return index-zero+1
dicCollection = []
ans = 0
for i,v in enumerate(s):
prev = dicCollection[-1][:] if dicCollection else [0]*26
prev[ ord(v)-ord('a') ] += 1
dicCollection.append(prev)
ans = max(ans,checkCorrect( prev,i ))
return ans
```