<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>

# DP approach: too slow

# class Solution:
#     def longestSubstring(self, s: str, k: int) -> int:
#       # for each letter, count # of occurrences in range (a, b)
#       # calculate longest (a, b) where each letter count is
#       #  either 0 or >= k.
#       # O(C * N^2)
#       n = len(s)
#       # dp[i][j][c]
#       dp = [[[0 for _ in range(26)] for _ in range(n)] for _ in range(n)]

#       # right inclusive range
#       # aaabb (0, 4] -> 'aaabb' (4, 4] -> 'b'
#       for i in range(n):
#         for j in range(i, n):
#           for c in range(26):
#             dp[i][j][c] = dp[i][j-1][c] + int(ord(s[j]) - ord('a') == c)
      
#       # print(dp)
#       max_seq = 0
#       for i in range(n):
#         for j in range(i, n):
#           seq = 0
#           for c in range(26):
#             seq += dp[i][j][c] == 0 or dp[i][j][c] >= k
#           if seq == 26:
#             max_seq = max(max_seq, j - i + 1)
#       return max_seq


from collections import Counter

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
      cnt = Counter(s)
      st = 0
      max_seq = 0
      if not s:
        return 0
      for i, c in enumerate(s):
        if cnt[c] < k:
          return max(
            self.longestSubstring(s[:i], k),
            self.longestSubstring(s[i+1:], k)
          )
      return len(s)


52861