Welcome to ShenZhenJia Knowledge Sharing Community for programmer and developer-Open, Learning and Share
menu search
person
Welcome To Ask or Share your Answers For Others

Categories

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

I have a solution as below. My questions:

  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;        
    }
    
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
thumb_up_alt 0 like thumb_down_alt 0 dislike
1.2k views
Welcome To Ask or Share your Answers For Others

1 Answer

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 implementation:

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]]

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
thumb_up_alt 0 like thumb_down_alt 0 dislike
Welcome to ShenZhenJia Knowledge Sharing Community for programmer and developer-Open, Learning and Share
...