[经典面试题][搜狗]在一个字符串中寻找包含全部出现字符的最小字串

题目

一个字符串中含有n个字符，其中有m个不同的字符，n>>m，用最少的时间和空间找到包含所有这m个字符的最短的字串，不考虑特殊字符，只考虑字母数字即可。
例如：
abccbaddac, 返回：cbad
aabcadbbbcca，返回：bcad

思路

[算法系列之二十二]包含T全部元素的最小子窗口
本题目相比连接中所说的稍微简单一些，本题目不用考虑重复字符。

代码

    /*---------------------------------------------
    *   日期：2015-02-24
    *   作者：SJF0115
    *   题目: 包含全部出现字符的最小字串
    *   来源：搜狗
    *   博客：
    -----------------------------------------------*/
    #include <iostream>
    #include <climits>
    using namespace std;

    string MinWindow(string S){
        int slen = S.size();
        if(slen <= 0){
            return "";
        }//if
        int minWinStart,minWinEnd;
        int minWinLen = INT_MAX;
        // 统计不同字符个数
        int m = 0;
        int needFind[256] = {0};
        for(int i = 0;i < slen;++i){
            needFind[S[i]] = 1;
        }//for
        for(int i = 0;i < 256;++i){
            if(needFind[i] == 1){
                ++m;
            }//if
        }//for

        int hasFound[256] = {0};
        int val;
        int count = 0;
        for(int start = 0,end = 0;end < slen;++end){
            val = S[end];
            ++hasFound[val];
            if(hasFound[val] <= 1){
                ++count;
            }//if
            // 找到一子串包含全部不同的字符
            if(count == m){
                int startEle = S[start];
                while(hasFound[startEle] > 1){
                    --hasFound[startEle];
                    ++start;
                    startEle = S[start];
                }//while

                int curWinLen = end - start + 1;
                if(minWinLen > curWinLen){
                    minWinLen = curWinLen;
                    minWinStart = start;
                    minWinEnd = end;
                }//if
            }//if
        }//for
        if(count != m){
            return "";
        }//if
        return S.substr(minWinStart,minWinEnd - minWinStart + 1);
    }

    int main() {
        string S("aabcadbbbcca");
        cout<<MinWindow(S)<<endl;
    }

引用：

[算法系列之二十二]包含T全部元素的最小子窗口

相似题目：

[LeetCode]76.Minimum Window Substring

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>