参考 

Find substring with K distinct characters(http://www.cnblogs.com/pegasus923/p/8444653.html)

Given a string and number K, find the substrings of size K with K-1 distinct characters. If no, output empty list. Remember to emit the duplicate substrings, i.e. if the substring repeated twice, only output once.

• 字符串中等题。Sliding window algorithm + Hash。此题跟上题的区别在于，子串中有一个重复字符。
• 思路还是跟上题一样，只是需要把对count的判断条件改成dupCount。当窗口size为K时，如果重复字符只有一个的话，则为结果集。对dupCount操作的判断条件，也需要改为>0, >1。

1 // 2 //  main.cpp 3 //  LeetCode 4 // 5 //  Created by Hao on 2017/3/16. 6 //  Copyright © 2017年 Hao. All rights reserved. 7 // 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 using namespace std;13 14 class Solution {15 public:16     vector
         
           subStringK1Dist(string S, int K) {17         vector
          
            vResult;18         19         // corner case20         if (S.empty()) return vResult;21         22         unordered_map
           
             hash;23 24 // window start/end pointer, hit count25 int left = 0, right = 0, dupCount = 0;26 27 while (right < S.size()) {28 if (hash[S.at(right)] > 0) // hit the condition dup char29 ++ dupCount;30 31 ++ hash[S.at(right)]; // count the occurrence32 33 ++ right; // move window end pointer rightward34 35 // window size reaches K36 if (right - left == K) {37 if (1 == dupCount) { // find 1 dup char38 if (find(vResult.begin(), vResult.end(), S.substr(left, K)) == vResult.end()) // using STL find() to avoid dup39 vResult.push_back(S.substr(left, K));40 }41 42 // dupCount is only increased when hash[i] > 0, so only hash[i] > 1 means that dupCount was increased.43 if (hash[S.at(left)] > 1)44 -- dupCount;45 46 -- hash[S.at(left)]; // decrease to restore occurrence47 48 ++ left; // move window start pointer rightward49 }50 }51 52 return vResult;53 }54 };55 56 int main(int argc, char* argv[])57 {58 Solution testSolution;59 60 vector
            
              sInputs = { "aaabbcccc","awaglknagawunagwkwagl", "abccdef", "", "aaaaaaa", "ababab"};61 vector
             
               iInputs = { 4, 4, 2, 1, 2, 3};62 vector
              
                result;63 64 /*65 {abbc }66 {awag naga agaw gwkw wkwa }67 {cc }68 {}69 {aa }70 {aba bab }71 */72 for (auto i = 0; i < sInputs.size(); ++ i) {73 result = testSolution.subStringK1Dist(sInputs[i], iInputs[i]);74 75 cout << "{ ";76 for (auto it : result)77 cout << it << " ";78 cout << "}" << endl;79 }80 81 return 0;82 }