查找N个唯一字符的最长子串 [英] Find longest substring of N unique characters

问题描述

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

Input: str="abcdeefuiuiwiwwaaaa" n=3 output: "iwiwwaaaa" (longest substr with 3 diff chars)

我有一个解决方案，下面。我的问题：

I have a solution as below. My questions:

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



2. 下面的解决方案无法解决整个ASCII，是否可以在没有额外空间的情况下改进它？

1. How is the time complexity? I know it must be better than O(n^2), but not sure whether can conclude it's O(n).

2. The solution below can not cover the whole ASCII, can we improve this without additional space?

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 遍历数组，并跟踪数字<$ c $在 S [i] 和 S [j] 之间用不同的字母c> K 。每当此数字小于或等于 n 时，递增 j 并递增 i 每当 K 大于 n 时。还请记住， K 等于 n 的最长子字符串。

There is an O(n). Let S be the string. Just go through the array with two pointers i and j and keep track of number K of different letters between S[i] and S[j]. Increment j whenever this number is smaller or equal n and increment i whenever K is greater than n. Also remember the longest substring for which K was equal to n.

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

In the implementation you also need a hash table to keep track of the last occurrence of the letter.

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个唯一字符的最长子串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！