Longest Substring with At Least K Repeating Characters

from collections import Counter

'''
suppose we have input as s="aaabbccddeeeddd" and k=3 here Counter(s)={a=3,b=2,c=2,d=5,e=3} so one thing is for sure that b and c can't come in the our Longest Substring so better split on b and c.
so now probable answers=[aaa,ddeeeddd] so we will check again on them here aaa is a good answer and then again ddeeeddd is also a good answer so it will be the answer.

Approach: We will break on the chars whose count is less than k because those chars with freq less than k can never be part of your answer so do the split on them now again, those splits are your probable answer and again check on them.
'''
from collections import Counter
def fun(s, k):
    if len(s) < k:
        return 0

    freq = Counter(s)
    ans = 0

    for ch in freq:
        if freq[ch] < k:
            probable_answers = list(s.split(ch))

            for p in probable_answers:
                ans = max(ans, fun(p, k))
            return ans   #return after split because this bad char can never be considered so no point of splitting on some other bad char because that will club these bad chars with anoter characters

    return len(s)   #this probable string s is valid

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) < k:
            return 0
        return fun(s,k)