algorithm - Find longest substring of N unique characters

Question

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;        
   }
   

Answer 1

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