题目：
Given a string s and an int k, return all unique substrings of s of size k with k distinct characters.
Example 1:
Input: s = "abcabc", k = 3 Output: ["abc", "bca", "cab"]Example 2:
Input: s = "abacab", k = 3 Output: ["bac", "cab"]Example 3:
Input: s = "awaglknagawunagwkwagl", k = 4 Output: ["wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag"] Explanation: Substrings in order are: "wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag", "wagl" "wagl" is repeated twice, but is included in the output once.Constraints:
The input string consists of only lowercase English letters [a-z]0 ≤ k ≤ 26这道题是要求出给定字符串的长度不超过k的substring，每个substring里所有字符都不一样。我能想到的最简单的办法就是全部遍历一遍每个字符，每次挑k个出来，然后看看这个substring里有没有重复的字符。代码很简单，大概是O(kn)，空间复杂度也是O(n)：
int main() { string s = "awaglknagawunagwkwagl"; int k = 4; vector<string> result; for (int i = 0; i < s.size() - k; i++) { string sub_str = s.substr(i, k); unordered_set<char> set; for (int j = 0; j < sub_str.size(); j++) { set.insert(sub_str[j]); } if (set.size() == k) { result.push_back(sub_str); } } for (int i = 0; i < result.size(); i++) { cout << result[i] << endl; } return 0; }看了别人的解法很多都是说什么sliding window之类的我还没看的东西，感觉好像很复杂的样子，不知道是不是我少考虑了哪些东西。
2020.09.09补
看了下sliding window的解法感觉还挺麻烦的，但是时间复杂度应该是O(n)，而直接用set因为每次都还要一个个把字符塞进set里所以是O(kn)。
Java版直接用set：
public static List<String> substringOfSizeKNaive(String s, int k) { List<String> result = new ArrayList<>(); for (int i = 0; i < s.length() - k; i++) { String substring = s.substring(i, i + k); Set<Character> set = new HashSet<>(); for (char c : substring.toCharArray()) { set.add(c); } if (set.size() == k - 1) { result.add(substring); } } return result; }用sliding window我看了两个解法，第一个解法看起来比较常规，维护left和right，保证窗口内的所有字符都是distinct的，如果窗口size为k就算找到了一个。但是这个做法没有办法扩展到substring of size k with k-1 distinct characters。
/** * Sliding Window for size k and k distinct * Make sure the window contains all unique character, and add it to the result if size is k * However, cannot be extended to size k with k - 1 distinct characters */ public static List<String> substringOfSizeKwithKDistinct(String s, int k) { List<String> result = new ArrayList<>(); int left = 0, right = 0; int[] chars = new int[26]; while (right < s.length()) { chars[s.charAt(right) - 'a']++; while (chars[s.charAt(right) - 'a'] > 1) { chars[s.charAt(left) - 'a']--; left++; } if (right - left + 1 == k) { result.add(s.substring(left, right + 1)); chars[s.charAt(left) - 'a']--; left++; } right++; } return result; }另外一个稍稍复杂一点点，只需要维护right就可以了因为我们保证窗口的size为k，也就相当于left是right - k + 1。最开始的前k个需要单独处理一下，后面的再开始while循环遍历到结尾。循环里刚开始踩了点坑，主要是下标，循环里最开始是已经更新后的right index，需要被加上，然后要减掉的left index应该是right - k，而不是新的substring的left index。然后也别忘了加加减减，嗯。
/** * Sliding Window for size k and k distinct * Make sure the window size is k * Count the number of distinct chars when window is sliding */ public static List<String> substringOfSizeK(String s, int k) { List<String> result = new ArrayList<>(); int[] chars = new int[26]; int count = 0; for (int i = 0; i < k; i++) { if (chars[s.charAt(i) - 'a'] == 0) { count++; } chars[s.charAt(i) - 'a']++; } if (count == k - 1) { result.add(s.substring(0, k)); } int right = k; while (right < s.length()) { chars[s.charAt(right) - 'a']++; if (chars[s.charAt(right) - 'a'] == 1) { count++; } int left = right - k; chars[s.charAt(left) - 'a']--; if (chars[s.charAt(left) - 'a'] == 0) { count--; } if (count == k - 1) { result.add(s.substring(left + 1, right + 1)); } right++; } return result; }
