分治和滑动窗口（自己加限制） 这一题很有启发意义，自己的分治不太会用，这一题如果想不到分治确实其他方法就不太好用了。
class Solution { public: int longestSubstring(string s, int k) { return helper(s, 0, s.size()-1, k); } private: int helper(string& s, int i, int j, int k) { if (j-i+1 < k) return 0; vector<int> count(26, 0); for (int idx = i; idx <= j; ++idx) count[s[idx]-'a']++; bool valid = true; for (int cnt : count) if (cnt > 0 && cnt < k) { valid = false; break; } if (valid) return j-i+1; for (int idx = i; idx <= j; ++idx) if (count[s[idx]-'a'] > 0 && count[s[idx]-'a'] < k) return max(helper(s, i, idx-1, k), helper(s, idx+1, j, k)); return 0; } };分治：1.子问题不重叠 2.拆分的时候不一定要是中间，可以是某个自己想要的位置
所谓的子问题不重叠，是真正的不重叠，一旦分开之后，要么是答案在两边中找（就像这一题），要么还要分开的一段位置也可能是答案。 而dp的子问题重叠就是：可能多个问题的求解会用到相同的子问题，所以要把相同的子问题存储起来。 然后像这里的分治，不会有多个问题有相同的子问题，因为分的很清楚，一个子问题只会被一个问题用到。
这一题如果感性来说的话应该是这么个思路： 递归求解，而不是从前到尾迭代（这种O(n)的想法有点贪了） 一段里面，有一些字母出现的不够，那么肯定不想要那些出现的不够的字母，那么应该除去那些不够的字母，在不包含它们的范围里迭代计算。
还是对分治理解的不够，估计之后还是不行
另外，上面是针对第一个不符合条件的来做分治，下面更加精细一点，把每个不符合条件的位置都剔除了，时间从152ms->4ms：
class Solution { public: int longestSubstring(string s, int k) { return helper(s, 0, s.size()-1, k); } private: int helper(string& s, int i, int j, int k) { if (j-i+1 < k) return 0; vector<int> count(26, 0); for (int idx = i; idx <= j; ++idx) count[s[idx]-'a']++; bool valid = true; for (int cnt : count) if (cnt > 0 && cnt < k) { valid = false; break; } if (valid) return j-i+1; int idx1 = i; int maxCnt = 0; while (idx1 <= j) { if (count[s[idx1]-'a'] < k) ++idx1; else { int idx2 = idx1; while (idx2 <= j && count[s[idx2]-'a'] >= k) ++idx2; maxCnt = max(maxCnt, helper(s, idx1, idx2-1, k)); idx1 = idx2; } } return maxCnt; } };所以这里做的分治，1.子问题不重叠，确实都“分的很开” 2.不仅仅是不一定要在中间分开，而且是不仅可以分一个位置，需要的话可以分多个位置。
这一题确实很有启发.
关键问题还是：怎么想到用“分开”的方法的？ 如果解决一个问题可以由子问题而来（比如这里的不符合条件的字符的左右边），那么就可以想到用分治或者dp的方法，不重叠是分治，重叠是dp（需要存储中间结果）。 也就是如果解决了子问题就是解决了问题本身，那么就用这种分治（或dp，需要存储）的方法。
另外，这一题有滑动窗口的做法，但是和平常的滑动窗口不一样。 这个方法是这样的：对于h:1->26，找到最大的子串中仅有h个不同的字符且每个字符数量都符合要求，这个子串就是一个可能的答案。
关键问题是为什么我们要引入“仅有h个不同的字符”这样的限制条件。 评论中有人是这样说的： 本质上还是暴力解法。滑动窗口问题中，难的是决定何时缩减窗口，也就是增加左边索引的值。所以为了对这一题使用滑动窗口的方法，我们得对窗口里面的子串施加限制，比如这里的不同字符的值。（如果没有限制的话，我们就不知道什么时候增加，什么时候缩减）。但是为了达到最后的正确结果，需要考虑所有的情况，也就是1-26都需要考虑到。
题目要求的问题本身（子串每个字符都>=k次）没有对窗口的子串提出明确的限制，也就是想要达到题目的要求可以拓展右边也可以缩减左边，不能确定怎么做，所以要想使用滑动窗口，就需要自己加以另外的限制。（这是这种做法的核心原因） （也就是我们也可以施加其他的条件，比如窗口的长度，但是这样需要考虑所有的可能的长度，这样太长时间）
class Solution { public: int longestSubstring(string s, int k) { int res = 0; for (int u = 1; u <= 26; ++u) res = max(res, helper(s, k, u)); return res; } private: int helper(string& s, int k, int u) { //s中子串内不同字符数量为u，且每一个数量都>=k的最长子串长度 int left = 0, right = 0; int numOfUnique = 0; int validNum = 0;//窗口内>=k的字符数量 int sz = s.size(); vector<int> counts(26, 0); int res = 0; while (right < sz) { ++counts[s[right]-'a']; if (counts[s[right]-'a'] == 1) ++numOfUnique; if (counts[s[right]-'a'] == k) ++validNum; if (numOfUnique > u) { while (numOfUnique > u) { --counts[s[left]-'a']; if (counts[s[left]-'a'] == 0) --numOfUnique; if (counts[s[left]-'a'] == k-1) --validNum; ++left; } } if (numOfUnique == u && validNum == numOfUnique) res = max(res, right-left+1); ++right; } return res; } };这题滑动窗口很有意思，可能以后也会用到这样的思想（自己加上限制使题目能够用滑动窗口）
