力扣76题，最小覆盖字串

力扣76题，最小覆盖字串

题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

输入输出样例

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

输入：s = "a", t = "a"
输出："a"

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

解法：滑动窗口

    string minWindow(string s,string t)
    {
    
        int slength=s.size();
        int tlength=t.size();

        //建立hash用以存储s,t字符中的值
        unordered_map<char,int>shash,thash;
        //将t字符串的字符保存到thash中
        for(char temp:t)
        {
    
            thash[temp]++;
        }

        //定义变量，左指针和右指针
        int left=0,right=0;
        //定义两字符串的差异值
        int distance=0;
        //最小字串的长度
        int minLen=slength+1;
        //起始位置的下标
        int begin=0;

        //建立滑动窗口

        while (right<slength)
        {
    
            char temp=s[right];
            //如果在字符串t中不存在s中对应的元素，则继续移动右指针
            if(thash.count(temp)==0)
            {
    
                right++;
                continue;
            }
            
            //将当前字符添加到hash表中，并移动右指针
            
            shash[temp]++;

            //distance 表示滑动窗口内部包含t中相同字符数目的个数，窗口内单个字符个数大于t中对应的字符个数的时候不再增加
            
            //判断字符之间的差异
            //如果s字符串中的等于字符串t中的字符串，继续增加
            if(shash[temp]==thash[temp])
            {
    
                distance++;
            }
            right++;
            //对于左指针进行处理，因为字符串t可以是重复的
            while(distance==thash.size())
            {
    
                //更新最小字符串的长度
                if(right-left<minLen)
                {
    
                    minLen=right-left;
                    begin=left;
                }

                //如果字符串t不存在s中对应的元素，则继续移动左指针
                char ltemp=s[left];

                if(thash.count(ltemp)==0)
                {
    
                    left++;
                    continue;
                }

                //s的字符ltemp数目恰好与t的数目相等，代表两者刚好满足,代表要出队
                if(shash[ltemp]==thash[ltemp])
                {
    
                    distance--;
                }
                shash[ltemp]--;
                left++;
            }
        }
        
        //根据最小长度的值是否改变则决定是否匹配成功
        return (minLen==slength+1)?"":s.substr(begin,minLen);
    }