问题：一个字符串S(暂时只考虑小写字母)，选择S中包含26种英文字母的最短子串，如果不包含则返回空字符分析：双指针，动态维护一个区间。尾指针不断往后扫，当扫到有一个窗口包含了所有26种英文字母的字符串后，再收缩头指针，直到不能再收缩为止。最后记录所有可能的情况中窗口最小的。
代码示例：
#include <algorithm>#include <string>#include <iostream>using namespace std;const int UPPERALPHA_MAX = 26;class Solution {public:int appeared_count[UPPERALPHA_MAX];public://判断是否已找到包含26种英文字母的字符串bool ContainAllAlpha(){for(int i=0;i<26;i++){if(appeared_count[i]<=0)return false;}return true;}//寻找符合条件的最小子串string minWindow(string S) {if (S.empty()) return "";if (S.size() < 26) return "";fill(appeared_count, appeared_count + UPPERALPHA_MAX, 0);size_t minWidth = INT_MAX, min_start = 0; // 窗口大小，起点int wnd_start = 0;//尾指针不断往后扫for (size_t wnd_end = 0; wnd_end < S.size(); wnd_end++) {appeared_count[S[wnd_end]-'a']++;//统计当前各英文字母出现的次数//当ContainAllAlpha()第一次为true后，其后的判断均为ture，后面程序运行的目的是找出最短的子串if(ContainAllAlpha()){ //如果为true则包含了所有的26个英文字母while(true){//如果重复出现了，可以后移if(appeared_count[S[wnd_start]-'a']>1){appeared_count[S[wnd_start]-'a']–;wnd_start++;}else //只出现了一次，停止后移break;}//找出最短子串，更新最短长度，，和最短长度的起点if (minWidth > (wnd_end – wnd_start + 1)) {minWidth = wnd_end – wnd_start + 1;min_start = wnd_start;}}}if(minWidth!=INT_MAX)return S.substr(min_start, minWidth);elsereturn "";}};int main(){string s="aabcdefghhhiijkijkjkijkkklmnopqrstuvzzzwxyzzcbabcdefghijklmnopqrstuvwxxyz";Solution solution;cout<<solution.minWindow(s)<<endl;}
输出结果为：abcdefghijklmnopqrstuvwxxyz
类似题目链接点击打开链接
如果你曾歌颂黎明，那么也请你拥抱黑夜
