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

Question

输入:str="abcdeefuiuiwiwwaaaa"n=3输出:“iwiwwaaaa”(具有 3 个差异字符的最长子字符串)

我有如下解决方案。我的问题:

1. 时间复杂度如何？我知道它一定比 O(n^2) 好，但不确定是否可以得出 O(n) 的结论。

2. 下面的解决方案无法涵盖整个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;        
   }
   

Answer 1

有一个 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]]