c - 在字符串 S 中找到最小窗口，它将包含字符串 T 的所有字符

Question

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

例如，

S = "ADOBECODEBANC"
T = "ABC"

最小窗口是 "BANC"。

void getstring(char str1[],char str2[],char hash[])
{

    int len=strlen(str1);
    int i=0,j;              //i keeps the previous index
    int min=INT_MAX;
    int cnt=0;  
    for(j=0;j<len;j++)
        {
            if(hash[str1[j]]==-1)   //means uninitialized, will be checked for first time only
            {

                cnt++;              
                hash[str1[j]]=j;                    

                if(cnt==1)
                i=j;

                int y=check(hash,str2); //checking for the characters
                //printf("y=%d",y);
                if(y)       //means all the characters are present
                {
                    if( (j-i+1)<min)
                    {
                    min=j-i+1;
                    I=i;
                    J=j;
                    }               


                }


               }
                else if(hash[str1[j]]>=0)
                {


                    hash[str1[j]]=j;



                    if(check(hash,str2) )
                    {                   

                    if( hash[str1[i]]==hash[str1[j]] )      //it means that we are moving the first
                    {                       //index only
                    i=getmin(hash,str2);    //get minimum index of the element              

                        if( (j-i+1)<min)
                        {
                            min=j-i+1;
                            I=i;
                            J=j;
                        }


                    }
                    //else
                    }
                    else
                    {
                    if( hash[str1[i]]==hash[str1[j]] )
                    i=hash[str1[i]];                        
                    }

                }//end of else-if
                }//end of for    
}

我已经使用散列为其编写了代码，即我将字符串 T 的字符的索引值保留在散列中并使用两个索引，只要我前面的任何字符与较低索引处的字符相同，我首先检查长度，然后更新索引。

这种方法在最坏的情况下需要 O(nk)。

n - is the number of characters in S
k - is the number of characters in T

是否有任何方法可以花费 O(n) 时间来解决这个问题？

Answer 1

所以通过 S 跟踪您最后一次看到 T 中的每个字母的时间。

在每个点上，最后看到的字母中最远的将界定窗口的左边缘(当前点是右边缘)。

在这些窗口中，只需跟踪目前看到的最小窗口即可。在算法结束时，这将是总体上最小的窗口。