在这个包含0、1和2的最小窗口问题中，你得到TLE了吗？

Question

问题链接：https://www.geeksforgeeks.org/problems/smallest-window-containing-0-1-and-2--170637/1

使用滑动窗口技术后得到 TLE，显然需要 O(N) 时间复杂度和空间 O(1)

我使用的方法给出了 TLE :

int smallestSubstring(string S) {
        // Code here
        unordered_map<char,int>mp;
        int l=0,r=0;
        int cnt=0;
        int minLen=INT_MAX;
        while(l<=r && r<S.length()){
            char curChar=S[r];
            if(mp[curChar]==0)
            cnt++;
            
            mp[curChar]++;
            
            if(cnt==3){
                
                //contract karde bhai
                while(mp[S[l]]>1){
                    mp[S[l]]--;
                    l++;
                }
                int cur=r-l+1;
                minLen=min(minLen,cur);
                
            }
            r++;
        }
        
        return minLen==INT_MAX?-1:minLen;
    }

Answer 1

在上面的问题中，您使用的地图似乎只需要很少的时间，但如果您可以在恒定的时间内完成该问题，为什么要花很少的时间呢！ 因此，我们将使用大小为 3 的数组，仅用于包含具有频率的不同字符。

int smallestSubstring(string S) {
        // Code here
        int mp[3]={0};
        int l=0,r=0;
        int cnt=0;
        int minLen=INT_MAX;
        while(l<=r && r<S.length()){
            char curChar=S[r];
            if(mp[(curChar-'0')%3]==0)
            cnt++;
            
            mp[(curChar-'0')%3]++;
            
            if(cnt==3){
                
                //contract karde bhai
                while(mp[(S[l]-'0')%3]>1){
                    mp[S[l]-'0']--;
                    l++;
                }
                int cur=r-l+1;
                minLen=min(minLen,cur);
                
            }
            r++;
        }
        
        return minLen==INT_MAX?-1:minLen;
    }