字元串的視窗滑動問題

問題：一個字元串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);
		else
			return "";
	}	
};

int main(){
	string s="aabcdefghhhiijkijkjkijkkklmnopqrstuvzzzwxyzzcbabcdefghijklmnopqrstuvwxxyz";
	Solution solution;
	cout<<solution.minWindow(s)<<endl;
}
           

輸出結果為：abcdefghijklmnopqrstuvwxxyz

類似題目連結點選打開連結