<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 {
public:

    int dfs(const string& s, int l, int r, int k) {
        // std::cout << "dfs l = " << l << " r = " << r << std::endl;
        unordered_map<char, int> cnt;
        unordered_set<char> removed_char;
        for (char x = 'a'; x <= 'z'; ++x) {
            cnt[x] = 0;
        }
        for (int i = l; i < r; ++i) {
            if (!removed[i]) {
                cnt[s[i]]++;
            }
        }
        for (char x = 'a'; x <= 'z'; ++x) {
            if (cnt[x] < k) {
                removed_char.insert(x);
            }
        }
        int last_removed = -1;
        int ans = -1;
        for (int i = l; i < r; ++i) {
            if (!removed[i]) {
                if (removed_char.contains(s[i])) {
                    removed[i] = true;
                    if (last_removed == -1) {
                        ans = max(ans, dfs(s, l, i, k));
                    } else {
                        ans = max(ans, dfs(s, last_removed, i, k));
                    }
                    last_removed = i;
                }
            }
        }
        if (last_removed == -1) {
            ans = 0;
            for (int i = l; i < r; ++i) {
                if (!removed[i]) {
                    ans++;
                }
            }
            // std::cout << "dfs l = " << l << " r = " << r << " return = " << ans << std::endl;
            return ans;
        } else {
            ans = max(ans, dfs(s, last_removed, r, k));
            // std::cout << "dfs l = " << l << " r = " << r << " return = " << ans << std::endl;
            return ans;
        }
    }

    int longestSubstring(string s, int k) {
        removed = vector<bool>(s.size(), false);
        int ans = dfs(s, 0, s.size(), k);
        return ans;
    }
    vector<bool> removed;
};

/*
 time O(V * N)
 space O(V * N)
 */
31480