Найти самую длинную подстроку N уникальных символов

Question

Входной сигнал: ул = «abcdeefuiuiwiwwaaaa» п = 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]] 

Answer 2

Ваш нынешний код сложность O (N^2), так как вы используете для вложенной петли для проверки подстрок, которые начинаются с каждого символа.

IMO вы можете сделать это в O (N * к) времени и О (А) дополнительное пространство (где к = количество уникальных символов разрешено):

1. Iterate строка с самого начала и добавить 1-й символ в карте значения для последней найденной позиции.
2. Продолжайте анализировать строку и обновлять последнюю позицию, найденную для каждого символа на карте.
3. Когда вы получаете новый символ, увеличивайте количество символов и создайте последнюю позицию для этого символа = текущая позиция.
4. Когда число на карте достигает k, повторите команду map и найдите значение индекса минимальной позиции. вычислите present position - min(last position index) и соответствующим образом обновите подстроку максимальной длины. Сокращение. Выньте этого персонажа с карты.
5. Продолжите выше, пока не достигнете конца строки.

Answer 3

Ниже мой подход к решению этого вопроса. Прежде всего, он разбивает строку на группы одинаковых символов; Затем петли для извлечения всех допустимых подстрок; наконец, возвращает все возможные длинные подстроки:

import re 
def longest(S,n): 
    # 1. groupby unique characters 
    grp_S = [ s[0] for s in re.findall(r'(([a-z])\2*)', S)] 
    # 2. retrieve all valid combinations in tuples (characters count, substring) 
    options = [] 
    for i in xrange(len(grp_S)): 
     g = 0 
     while i + n + g <= len(grp_S): 
      if (len(set([x[0] for x in grp_S [i: i + n + g]])) == n and i + n + g + 1 > len(grp_S)) or \ 
       (len(set([x[0] for x in grp_S [i: i + n + g]])) == n and len(set([x[0] for x in grp_S [i: i + n + g + 1]])) > n): 
       options.append((len(''.join(grp_S [i: i + n + g])), ''.join(grp_S [i: i + n + g]))) 
       break 
      else: g = g + 1 
    # 3. return the list of all longest substrings 
    return [ v[1] for v in options if v[0] == max(options)[0] ] 

Answer 4

Простой с не проверяя никаких ошибок в короткий синтаксис питона

Answer 5

Все ответы являются слишком сложными. Я брошу легкое решение.

Констриант проблемы вращается вокруг ДИСКРИТСКИХ ХАРАКТЕР.

-Наше решение в приоритетном порядке должно уделять приоритетное значение УНИКАЛЬНОГО символа (unicount) в любое время.

-Всмотрите на два случая. Один из них - либо unicount < K, либо unicount> = K.

CASE 1: (unicount<K) 
    1a: Str[i] is a new character not present already in the current window. 
     --Increase unicount and hash[str[i]] 
    1b: Str[i] is a not new character present already in the current window. 
     --No need to increase unicount. Just hash str[i]. 

CASE 2: (unicount>=K) 
    2a. Str[i] is a not new character present already in the current window. 
     --No need to do anything cause unicount will be equal to K. Just hash str[i]. 
    2b. Slide the window (VARIABLE start) till the unicount value decreases.. 
     --Now similar to case 1. 

Ниже код печатает самую длинную длину такой подстроки только с K различными символами. Его легко изменить, чтобы на самом деле распечатать такую ​​подстроку.

int printLengthKUniqueSubstring(string str,int k) 
{ 
    int hash[256] = {0}; 

    int n = str.length(); 
    int unicount = 0,maxlength = 0,start = 0; 
    for(int i=0;i<n;i++) 
    { 
     if(unicount<k) 
     { 
      if(hash[str[i]]==0) 
      { 
       hash[str[i]]++; 
       unicount++; 
      } 
      else 
       hash[str[i]]++; 
     } 
     else 
     { 
      // cout<<"hello "<<" "<<unicount<<" "<<i<<endl; 
      if(hash[str[i]]>0) 
       hash[str[i]]++; 
      else 
      { 
       while(unicount>=k) 
       { 
        hash[str[start]]--; 
        if(hash[str[start]]==0) 
         unicount--; 
        start++; 
       } 
       if(hash[str[i]]==0) 
       { 
        hash[str[i]]++; 
        unicount++; 
       } 
       else 
        hash[str[i]]++; 
      } 

     } 
     maxlength = max(maxlength,i-start+1); 
    } 
    if(unicount<k) 
     return -1; 
    return maxlength; 
} 

Имейте славный день!

Answer 6

Сложность O(n*C) где C является константой для проверки ключа для минимального значения словаря.

Вот решение на C#.

public static string GetLongestSubString(string s, int numberOfUniqueChar) 
{ 
    char c; 
    int start = 0; 
    string result = string.Empty, temp = string.Empty; 
    Dictionary<Char, int> dic = new Dictionary<char, int>(); 

    for (int i = 0; i < s.Length; i++) 
    { 
     if (!dic.ContainsKey(s[i])) 
     { 
      dic.Add(s[i], i); 
      if (dic.Count > numberOfUniqueChar) 
      { 
       temp = s.Substring(start, (i - start)); 
       if (temp.Length > result.Length) 
       { 
        result = temp; 
       } 
       c = dic.OrderBy(k => k.Value).FirstOrDefault().Key; 
       start = dic[c]+1; 
       dic.Remove(c); 
      } 
     } 
     else 
     { 
      // increase index of the current key 
      dic[s[i]] = i; 

      //if last char not change then check current substring with the result 
      if(i==s.Length-1){ 
       temp = s.Substring(start); 
       if (temp.Length > result.Length) 
       { 
        result = temp; 
       } 
      } 
     } 
    } 

    return result; 
}