查找N个唯一字符的最长子串

问题内容：

输入：str =“ abcdeefuiuiwiwwaaaa” n = 3输出：“ iwiwwaaaa”（最长的substr，带有3个差异字符）

我有以下解决方案。我的问题：

时间复杂度如何？我知道它一定比O（n ^ 2）好，但是不确定是否可以得出O（n）。
下面的解决方案无法覆盖整个ASCII，是否可以在没有额外空间的情况下对此进行改进？

        public static String getSubstrOfMChars(String str, int m) 
    {
         if (str==null || str.length()==0)
             return "";     

         int len = str.length();        
         String max = "";

         for(int i=0; i<len;) 
         {  
             StringBuilder sb = new StringBuilder();
             int counter = 1;
             int checker = 0;
             char firstChar = str.charAt(i);
             int firstCharPos = i;    // first char position in the string
             sb.append(firstChar);
             checker |= 1 << (firstChar - 'a');

             for(int j=i+1; j<len; j++) 
             {  
                 char currChar = str.charAt(j);
                 if (currChar == firstChar) 
                     firstCharPos++;                

                 int tester = checker & (1<<(currChar - 'a'));
                 if ( tester > 0 ) // already have such character
                 {
                     sb.append(currChar);
                     continue;
                 }

                 // new character
                 if (++counter > m) 
                 {
                    i = firstCharPos + 1;

                    if (sb.length() > max.length()) 
                    {
                        max = sb.toString();
                    }
                    break;
                 }
                 sb.append(currChar);                   
                 checker |= 1 << (currChar - 'a');              
            }

            if (counter <= m) 
            {               
                if ((counter==m) && sb.length() > max.length()) 
                {
                    max = sb.toString();
                }               
                break;
            }

         }

         return max;        
    }

问题答案：

有一个O（n）。让S是字符串。刚去通过阵列有两个指针i和j并跟踪数K之间不同的字母S[i]和S[j]。增量j每当这个数小于或等于n和增量i每当K大于n。还要记住最长的子字符串K等于n。

在实现中，您还需要一个哈希表来跟踪字母的最后一次出现。

Python实现：

def longest(S,n):
    i = j = K = 0
    res = (0,0)
    last = {}

    while i < len(S):
        # if current substring is better than others than save
        if K == n and j - i > res[1] - res[0]:
            res = (i,j)

        # if we reach the end of the string, we're done.
        if j + 1 > len(S):
            break
        # if we can go further with the right end than do it
        elif K <= n and j + 1 <= len(S):
            if not last.has_key(S[j]):
                K = K + 1
            last[S[j]] = j
            j = j + 1
        # if we must go further with the left end than do it
        else:
            if last.has_key(S[i]):
                del last[S[i]]
                K = K - 1
            i = i + 1
    return S[res[0]:res[1]]

查找N个唯一字符的最长子串

微信关注