<p>Given a string <code>s</code> and an integer <code>k</code>, return <em>the length of the longest substring of</em> <code>s</code> <em>such that the frequency of each character in this substring is greater than or equal to</em> <code>k</code>.</p>

<p data-pm-slice="1 1 []">if no such substring exists, return 0.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaabb&quot;, k = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> The longest substring is &quot;aaa&quot;, as &#39;a&#39; is repeated 3 times.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ababbc&quot;, k = 2
<strong>Output:</strong> 5
<strong>Explanation:</strong> The longest substring is &quot;ababb&quot;, as &#39;a&#39; is repeated 2 times and &#39;b&#39; is repeated 3 times.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>
	<li><code>s</code> consists of only lowercase English letters.</li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        # index each char, e.g. 'a' -> [3, 5, 6]
        hash_fn = lambda c: ord(c) - 97 # char -> array index

        def helper(s, k, left, right):

            # substring is smaller than k there are no chars with freq > k
            if right - left < k:
                return 0

            # find *all* invalids (and there indices)
            indices = [[] for _ in range(26)] # locations of each char
            # invalid_set = set(s[left:right]) # chars with not enough occurances in substring
            invalid_set = set()
            for i in range(left, right):
                c = s[i]

                # update char index
                c_ids = indices[hash_fn(c)]
                c_ids.append(i)

                # update invalid set
                if len(c_ids) < k:
                    invalid_set.add(c)
                elif c in invalid_set:
                    invalid_set.remove(c)
                
            # if all chars are valid, your done
            if len(invalid_set) == 0:
                return right - left

            # otherwise, compile list of all indices of all invalids
            invalid_ids = [idx for c in invalid_set for idx in indices[hash_fn(c)]]
            # invalid_ids = []
            # for c in invalid_set:
            #     invalid_ids += indices[hash_fn(c)]

            # recurse on all substrings between invalids (exclusive)
            invalid_ids += [right]
            # invalid_ids.sort()
            end = left - 1
            maxLength = 0
            for i in invalid_ids:
                start, end = end+1, i
                maxLength = max(maxLength, helper(s, k, start, end))

            return maxLength

        return helper(s, k, 0, len(s))
18046