最小覆盖子串

class Solution {
public:
    string minWindow(string S, string T) {
        // 思路是在S中选一个T中的元素作为起点，来计算最短窗口
        if(S == ""|| T == "")
            return "";
        int tlen = T.size();
        int slen = S.size();
        if(tlen > slen)
            return "";
        multiset<char> Tset;  // 存T中的元素
        for(int i = 0; i < tlen; i++)
            Tset.insert(T[i]);
        int min = 10000;  // 最短窗口长度
        int bindex = 10000; // 窗口的起点
        for(int i = 0; i <= slen-tlen; i++)
        {
            if(Tset.find(S[i]) == Tset.end())  // 找一个起点
                continue;
            int begindex = i;
            multiset<char> Ts = Tset;
            int j = begindex;
            for(  ;!Ts.empty() && j < slen;j++)
            {
                auto iter = Ts.find(S[j]);
                if(iter != Ts.end())
                    Ts.erase(iter);
                // 直接用Ts.erase(S[j])会删掉所有值为S[j]的节点
            }
            if(Ts.empty())
            {
                int temp = j-begindex;
                if(min > temp)   // 更新最短长度
                {
                    min = temp;
                    bindex = begindex;
                }
            }
        }
        if(bindex == 10000)
            return "";
        return S.substr(bindex,min);
    }
};

这道题的思路是：
1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。
记录窗口长度d
2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
包含在窗口，
3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
4) 如此循环知道end到S中的最后一个字符。
时间复杂度为O(n)
public class Solution {
    public String minWindow(String S, String T) {
        int[] map = new int[128];
        //init map, 记录T中每个元素出现的次数
        for(int i = 0; i < T.length(); i++) {
            map[T.charAt(i)]++;
        }

        // begin end两个指针指向窗口的首位，d记录窗口的长度， counter记录T中还有几个字符没被窗口包含
        int begin = 0, end = 0, d = Integer.MAX_VALUE, counter = T.length(), head = 0;
        // end指针一直向后遍历
        while(end < S.length()) {
            // map[] > 0 说明该字符在T中出现，counter-- 表示对应的字符被包含在了窗口，counter--, 如果s中的字符没有在T中出现，则map[]中对应的字符-1后变为负值
            if(map[S.charAt(end++)]-- > 0) {
                counter--;
            }
            // 当counter==0时，说明窗口已经包含了T中的所有字符
            while (counter == 0) {
                if(end - begin < d) {
                    d = end - (head = begin);
                }
                if(map[S.charAt(begin++)]++ == 0) {  // begin开始后移，继续向后寻找。如果begin后移后指向的字符在map中==0，表示是在T中出现的，如果没有出现，map[]中的值会是负值。
                    counter++;                      // 在T中的某个字符从窗口中移除，所以counter++。
                }
            }
        }
        return d==Integer.MAX_VALUE ? "" :S.substring(head, head+d);
    }
}

滑动窗口

在jerry之前的算法题解中，也是有过滑动窗口解法的题目。

传送门：[Leetcode-3] 无重复字符的最长子串

• 滑动窗口，是一种框架思维：
  • 用l,r表示滑动窗口的左边界和右边界，通过改变l,r来扩展和收缩滑动窗口
• 在这题目中可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串t的所有元素，记录下这个滑动窗口的大小slze = r-l+1，这些长度中的最小值就是要求的结果。
• 主要分以下几个步骤：

1. 从0开始，不断增加r使滑动窗口增大，直到窗口包含了t的所有元素
2. 从0开始，不断增加l使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的大小，并保存最小值 mln
3. 让l再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤1开始执行，寻找新的满足条件的滑动窗口，如此反复，直到r超出了字符串S范围
4. 判断滑动窗口是否包含了t中的所有元素，这是将考虑的最关键的一部分！！！

• 这里使用一个字典来记录t中的字符以及个数，还有所需个数
• 用need[128]来记录t中字符，字符将以ASCII形式存储
• 用needCount表示当前遍历下，满足t还需要的元素个数
• need[97]=2表示t中需要2个字符a，needCount=3表示覆盖t还需要3个字符
• 每当遍历到t中的字符，其对应的need[]应该-1
• 当needCount==0时，则当前窗口覆盖了t中所有元素

5. 其次关键是如何判断当前遍历的字符是不是多余的字符？要是多余，就可以移除。

• 在这里，我对上面的字典need[]多加一步操作
• 无论当前遍历字符在不在t中，都要在need中-1
• 要是多余字符，其对应的need[]一定是<0
• 这样的目的：利用need[]的正负来区分字符是否多余的还是有用的

6. 最后一点，无论左边界还是右边界，在边界移动时候，要注意维护对应的参数。

class Solution {
    public String minWindow(String s, String t) {
        // l(left): 左边界
        // r(right): 右边界
        int l = 0, r = 0;
        // size=r-l+1: 滑动窗口的大小，默认值Integer.MAX_VALUE方便值交换
        int size = Integer.MAX_VALUE;
        // needCount: 当前遍历下，满足t还需要的元素个数，默认值、最大值是t.length，为0时表示滑动窗口内容覆盖了t中所有元素
        int needCount = t.length();
        // start: 记录有效滑动窗口的起始位置(左边界)，方便后续查找对应的字串
        int start = 0;
        // 字典need: 记录滑动窗口中需要t中各个元素的数量
        // ASCII方式存储 [A-Z]：65-90  [a-z]：97-122
        // need[97]=2 表示t中需要2个a
        // t中对应字符的need[]必须>=0
        // 若need[]<0表示是个多余的字符
        int[] need = new int[128];
        // 根据t的内容，向字典need添加元素
        for (int i = 0; i < t.length(); i++)
            need[t.charAt(i)]++;
        // 循环条件，右边界不能溢出
        while (r < s.length()) {
            // 获取当前遍历的元素字符
            char c = s.charAt(r);
            // 若当前遍历字符是t中的内容，needCount需要-1
            if (need[c] > 0)
                needCount--;
            // 无论c在不在t中，都要在need中-1
            // 目的：利用正负来区分字符是否多余的还是有用的
            need[c]--;
            // needCount==0表示当前窗口满足t中所有元素
            if (needCount == 0) {
                // 判断左边界是否可以收缩
                // 如果l对应字符的need[]<0，表示是个多余的字符
                while (l < r && need[s.charAt(l)] < 0) {
                    // 在need[]中维护更新这个字符
                    need[s.charAt(l)]++;
                    // 左边界向右移，移除这个多余字符
                    l++;
                }
                // 判断是否更新有效滑动窗口的大小
                if (r - l + 1 < size) {
                    // 更新
                    size = r - l + 1;
                    // 记录有效滑动窗口的起始位置(左边界)，方便查找对应的字串
                    start = l;
                }
                // 左边界对应的字符计数需要+1
                need[s.charAt(l)]++;
                // 重新维护左边界
                l++;
                // 重新维护当前的needCount
                needCount++;
            }
            // 右边界向右移，寻找下一满足条件的有效滑动窗口
            r++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}

时间复杂度：。左右指针各自扫一遍字符串s，时间复杂度是。

空间复杂度：。只用到一个字典用于记录的数组，长度128。

class Solution {
public:
    string minWindow(string S, string T) {
        string result;
        map<char,int>t,s;
        for(auto c:T)
        	t[c]++;
        int count=0,l=0;
        for(int r=0;r<S.length();r++)
        {
        	if(t[S[r]] != 0)
        	{
        		s[S[r]]++;
        		if(s[S[r]] <= t[S[r]])
        			count++;
        		while(count == T.length())
        		{
        			if(result.empty() || result.length()>r-l+1)
        				result = S.substr(l,r-l+1);
        			if(t[S[l]])
        			{
        				s[S[l]]--;
        				if(s[S[l]] < t[S[l]])
        					count--;
					}
					l++;
				}
			}
		}
		return result;
    }
};

class Solution {
public:
    //维持一个窗口滑动，左边是left，右边是right，然后判断是否包含T
    string minWindow(string S, string T) 
    {
        string result;
        if(!S.size() || !T.size())
        {
            return result;
        }
        map<char, int>Tmap;	//存储T字符串里字符，便于与S匹配
        int left = 0;		//左边窗口,起始为0
        int count = 0;		//计数器，对窗口内T串字符数量进行计数,起始为0
        //装载T串
        int minlen = S.size() + 1;		//最小窗口，便于比较最后取最小的,初始化取最大
        for(int i = 0; i < T.size(); ++i)
        {
            Tmap[T[i]]++;
        }
        //移动右边窗口
        for(int right = 0; right < S.size(); ++right)
        {
            if(Tmap.find(S[right]) != Tmap.end())	//当窗口内部有T中的字符
            {
                if(Tmap[S[right]] > 0)
                {
                	count++;			//计数器+1
                }
                Tmap[S[right]]--;	//去掉包含的，剩下都是没包含的
                while(count == T.size())//当窗口内有T的所有字符，就要开始移动左窗口啦
                {
                    if(Tmap.find(S[left]) != Tmap.end())
                    {
                        //好了，这就是一个包含字符串的窗口范围：left ~ right, 
                        //判断是否比当前窗口还小，是就取串
                        if(minlen > right - left + 1)
                        {
                            //更新窗口大小
                            minlen = right -left + 1;
                            result = S.substr(left, right - left + 1);
                        }
                        //舍弃窗口左边字符串，继续移动窗口
                        Tmap[S[left]]++;
                        if(Tmap[S[left]] > 0)			//如果左边连续相同，则count不递减，窗口需要继续向右移动
                        {
                            count--;
                        }
                    }
                    left++;				//移动左窗口
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    string minWindow(string S, string T) {
        //滑动窗口
        unordered_map<char, int> ori,cur;
        for(auto& x:T){
            ori[x]++;
        }
        string res;
        int count=0;
        //i代表右窗口,j代表左边窗口
        for(int i=0,j=0;i<S.size();i++){
            cur[S[i]]++;
            if(cur[S[i]]<=ori[S[i]]) count++;//存在该字符个数加1
            //说明左窗口的字符在右边的位置可以替代,我们需要缩减窗口
            while(cur[S[j]]>ori[S[j]]) cur[S[j++]]--;//左窗口移动并减少字符个数
            //重复寻找最小的子串
            if(count==T.size()){
                if(res.empty()||i-j+1<res.size()){
                    res=S.substr(j,i-j+1);
                }
            }
        }
        return res;
    }
};

//主要思路是通过两次遍历找到所有可能的窗口（即从S中从start到end包含一个T），通过以下几个步骤实现：
//为了减少时间复杂度，用map记录T中所有字符出现的次数，使用count在S中寻找时计数，一旦找到一个T中的字符
//就count++，同时map中当前字符的次数减1，当count等于T的长度时，即找到了一个包含T的字符串，然后
//通过比较每个找到的字符串的长度，选择最短字符串，即为题中所求
class Solution {
public:
    string minWindow(string S, string T) {
        int len = T.size();
        int count = 0;
        int lenS = S.size();
        int start=0,end=lenS;
        for(int i=0;i<lenS;i++)
        {
            map<char,int> mp;
            for(int i=0;i<len;i++)
                mp[T[i]] += 1;
            if(mp[S[i]]>0)
            {
                count = 0;
                for(int j=i;j<lenS;j++)
                {
                    if(mp[S[j]]>0)
                    {
                        count++;
                        mp[S[j]]--;
                    }
                    if(count==len)
                    {
                        if(j-i<end-start)
                        {
                            start = i;
                            end = j;
                        }
                        break;
                    }
                }
            }
        }
        if(start>=0 && end<lenS)
            return S.substr(start,end-start+1);
        return "";
    }
};

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public String minWindow(String s, String t) {
		if (s == null || t == null || s.length() < t.length())
			return "";
		// HashMap的key为t中各个字符，value为对应字符个数
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		for (char c : t.toCharArray()) {
			if (!map.containsKey(c))
				map.put(c, 0);
			map.put(c, map.get(c) + 1);
		}
		// minLeft为最小窗口左下标，minLen为最小长度，count用来计数
		int minLeft = 0, minLen = s.length() + 1, count = 0;
		int left = 0;
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (map.containsKey(c)) {
				// 如果map.get(c)说明t中还有字符没有包含，计数器+1
				if (map.get(c) > 0){
					count++;
				}
				map.put(c, map.get(c) - 1);
			}
			// 如果left到i中包含t中所有字符
			while (count == t.length()) {
				if (i - left + 1 < minLen) {
					minLeft = left;
					minLen = i - left + 1;
				}
				c = s.charAt(left);
				if (map.containsKey(c)) {
					map.put(c, map.get(c) + 1);
					if (map.get(c) > 0)
						count--;
				}
				left++;
			}
		}
		if (minLen > s.length())
			return "";

		return s.substring(minLeft, minLeft + minLen);
	}
}

贴个Java的，参照了某位同志的思路
public class Solution {
// 从头开始检查S，如果是T中的元素，计算如果以该元素作为窗口的第一个元素
    public String minWindow(String S, String T) {
        if(S == null || S.length() <= 0 || T == null || T.length() <= 0)
        	return "";
        
        int[] sCount = new int[256];
        int[] tCount = new int[256];
        for(int i = 0; i < T.length(); i++){
        	tCount[(int)T.charAt(i)]++;
        }
        int begin = 0, e_begin = 0;
        int end = S.length(), e_end = S.length();
        for(int i = 0; i < S.length(); i++){
        	// 计算以S.charAt(i)开头的最小窗口
        	// S.charAt(i)不是T中字符，肯定不会是开头
        	if(tCount[S.charAt(i)] == 0)
        		continue;
        	sCount[S.charAt(i)]++;
        	end = i;
        	boolean isFind = true;
        	for(int j = 0; j < 256; j++){
        		if(sCount[j] < tCount[j]){
        			isFind = false;
        			break;
        		}
        	}
        	// 找到了T中所有字符
        	if(isFind){
        		// 找到S中包含T中字符的开头
        		while(begin < S.length()){
        			int ch = S.charAt(begin);
        			if(tCount[ch] == 0){
        				begin++;
        				continue;
        			}
        			// 如果ch出现次数超了，那么开头指针往后
        			if(sCount[ch] - 1 >= tCount[ch]){
        				sCount[ch]--;
        				begin++;
        			}
        			else {
						break;
					}
        		}
        		// 更新最小窗口的长度
        		if(e_end - e_begin > end - begin){
        			e_end = end;
        			e_begin = begin;
        		}
        	}
        }
        if(e_end - e_begin >= S.length())
        	return "";
        else
        	return S.substring(e_begin, e_end + 1);
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // 存放目标字符串的字符数量
        int[] need = new int[128];
        for (int i = 0; i < T.length(); i++) need[T.charAt(i)]++;
        // 目标字符串中的字符个数
        int count = T.length();
        // 左右指针,用于维护滑动窗口
        int left = 0, right = 0;
        // 记录窗口的起点与长度,用于截取字符串;长度初始化为一个不可能的最大值
        int start = 0, len = S.length() + 1;

        while (right < S.length()) {
            // 滑动窗口右侧
            char c = S.charAt(right++);
            // 仅当前字符的需要数量大于0时,需要的目标字符数量减一
            if (need[c] > 0) {
                count--;
            }
            // 所有字符都进行自减操作,不需要的字符会被减到负数,需要的字符先减到0,再减到负数
            need[c]--;

            // 当count为0时,说明当前窗口中的字符可以覆盖目标字符串T
            if (count == 0) {
                // 当need中,窗口左侧的字符为负数时,说明该字符是多余的(不论是否是T中包含的字符),滑动窗口左侧,直至最左侧的字符非多余,此时窗口为右侧固定情况下的最小覆盖子串
                while (need[S.charAt(left)] < 0) {
                    need[S.charAt(left++)]++;
                }
                // 判断长度,并记录起点和长度
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }
                // 将窗口左侧字符滑出,need中该字符需要的数量自增(为1)
                need[S.charAt(left++)]++;
                // 需要的目标字符数量也自增(为1)
                count++;
            }
        }
        // 若长度仍为不可能的最大值,说明没有覆盖子串,否则通过start和len进行截取
        return len == S.length() + 1 ? "" : S.substring(start, start + len);
    }
}

class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // 时间复杂度O(N)，空间复杂度O(N)
        unordered_map<char, int> tm, sm;
        for (char &c : T) tm[c]++;
        int left = 0, right = 0, start = -1, end = S.size();
        while (right <= S.size()) {
            if (check(tm, sm)) {
                if (sm.count(S[left])) --sm[S[left]];
                if (right - left < end - start) {
                    start = left;
                    end = right;
                }
                ++left;
            } else {
                if (tm.count(S[right])) ++sm[S[right]];
                ++right;
            }
        }
        return start == -1 ? "" : S.substr(start, end - start);
    }
    bool check(unordered_map<char, int> &tm, unordered_map<char, int> &sm) {
        for (auto &ele : tm)
            if (ele.second > sm[ele.first]) return false;
        return true;
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        m, M = -1, len(S)
        left, right = 0, 0
        sdict, tdict = {}, {}
        for i in T:
            if i in tdict.keys():
                tdict[i] = tdict[i] + 1
            else:
                tdict[i] = 1
        while right < len(S):
            if S[right] in tdict.keys():
                if S[right] in sdict.keys():
                    sdict[S[right]] = sdict[S[right]] + 1
                else:
                    sdict[S[right]] = 1
            else:
                right = right + 1
                continue
            right = right + 1
            flag = False
            for i in tdict.keys():
                if i in sdict.keys():
                    if tdict[i] > sdict[i]:
                        flag = True
                else:
                    flag = True
            if flag:
                continue
            while left < right:
                if M-m > right - left:
                    m, M = left, right
                tmp = S[left]
                left = left + 1
                if tmp in sdict.keys():
                    if sdict[tmp] > 1:
                        sdict[tmp] = sdict[tmp] - 1
                        if sdict[tmp] < tdict[tmp]:
                            break
                    else:
                        sdict.pop(tmp)
                        break
        if m == -1:
            return ''
        ret = S[m:M]
        return ret

public String minWindow (String S, String T) {
    // 统计目标字符个数（由于大小写都存在，懒得进行判断转换，直接存对应Ascii码，'z'最大）
    int[] tCharCount = new int['z'+1];
    for (char c : T.toCharArray()) {
        tCharCount[c] ++;
    }
    // 左右指针滑动窗口
    int hitTimes = 0;
    int minLen = Integer.MAX_VALUE;
    String result = "";
    for (int left = 0, right = 0; right < S.length(); right++) {
        tCharCount[S.charAt(right)]--;
        // 命中目标字符
        if (tCharCount[S.charAt(right)] > -1) {
            hitTimes ++;
        }
        // 全部字符都命中
        if (hitTimes == T.length()) {
            // 移动左指针，直致有效字符
            while (tCharCount[S.charAt(left)] != 0) {
                tCharCount[S.charAt(left++)] ++;
            }
            // 记录最小值，以及对应字符
            if (right-left+1 < minLen) {
                result = S.substring(left, right+1);
                minLen = right - left + 1;
            }
            // 恢复最左有效数据，命中次数-1
            tCharCount[S.charAt(left++)] ++;
            hitTimes --;
        }
    }
    return result;
}

哈希表 + 双指针的滑动窗口，找到包含T的所有字符，缩小窗口找到最小子串
时间复杂度：O(len(T)*len(S)+len(T)) 空间复杂度：O(len(T))

class Solution:
    def check(self, mp):
        for key, value in mp.items():
            if value < 0:
                return False
        return True

    def minWindow(self , S: str, T: str) -> str:
        mp = {}
        low = 0
        high = 0
        left = -1
        right = -1
        len_ = len(S) + 1
        for i in T:
            if i in mp:
                mp[i] -= 1
            else:
                mp[i] = -1
        for j in range(len(S)):
            if S[high] in mp:
                mp[S[high]] += 1
                while self.check(mp):
                    if len_ > high - low + 1:
                        len_ = high - low + 1
                        left = low
                        right = high
                    if S[low] in mp:
                        mp[S[low]] -= 1
                    low += 1
            high += 1
        if left == -1:
            return ''
        return S[left:right+1]

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String s, String t) {
        HashMap<Character, Integer> window = new HashMap<>();
        HashMap<Character, Integer> need = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            Integer count = need.get(t.charAt(i));
            count = count == null ? 1 : ++count;
            need.put(t.charAt(i),count);
        }
        int left =0 , right = 0;
        int vaild = 0;
        int len = Integer.MAX_VALUE,start = 0;
        //最小覆盖字串起始索引
        while (right < s.length()){
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)){
                Integer count = window.get(c);
                count = count == null ? 1 : ++count;
                window.put(c,count);
                if (window.get(c).equals(need.get(c))){
                    vaild++;
                }
            }

            //都包含了，right找到了，可以考虑收缩
            while (vaild == need.size()){
                if (right -left < len){
                    start = left;
                    len = right - left;
                }
                //d是将要移出窗口的字符
                char d = s.charAt(left);
                //左移窗口
                left++;
                //数据更新
                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        vaild--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
    }
}

class Solution {
public:
    string minWindow(string S, string T) {
        int t[127] = {0};
        for (int i = 0; i < T.size(); i++) t[T[i]]++;
        int ok = 0;
        bool vis[127] = {0};
        for (int i = 0; i < 127; i++) if (t[i]) ok++, vis[i] = true;
        int mi = 1e9, mi_l = 0;
        for (int i = 0, j = 0; i < S.size(); i++) {
            for ( ; j < S.size() && ok; ++j) {
                if (vis[S[j]]) {
                    if (t[S[j]] == 1) --ok; //字母S[j]不需要了
                    --t[S[j]];
                }
            }
            if (ok == 0 && mi > j - i) {
                mi = j - i;
                mi_l = i;
            }
            //去掉S[i]
            if (vis[S[i]]) {
                if (t[S[i]] == 0) ++ok; //字母S[i]不够了
                ++t[S[i]];
            }
        }
        if (mi == 1e9) return "";
        else return S.substr(mi_l, mi);
    }
};

class Solution {
public:
    string minWindow(string s, string t) {
        int len = t.length();
        int size = s.length();
        if(size < len){
            return "";
        }
        
        int record[256] = {0};
        int freq[256] = {0};
       
        for(int i = 0; i < len; ++i){
            ++record[t[i]];
        }
        
        int i = 0;
        int j = -1;
        int sum = 0;
        int min_len = size;
        int cur = -1;
        while(i < size){
            if(sum < len && j+1 < size){
                                 ++freq[s[++j]];
                if(record[s[j]] && freq[s[j]] <= record[s[j]]){
                        ++sum;
                   }
               }                                               if(sum >= len){
                if(min_len >= j-i+1){
                    cur = i;
                    min_len = j-i+1;
                }
                --freq[s[i]];
                   if(record[s[i]] && record[s[i]] - freq[s[i]] >= 1){
                       --sum;
                }
                ++i;
            
               }
                               if(j == size-1 && sum < len)
                   break;
        }
        
        if(cur != -1){
            return string(s, cur, min_len);
        }else{
            return "";
        }
        
    }
};