Поиск самой длинной подстроки без повторения в строке. Сложность времени?

Question

Недавно я дал интервью компании, занимающейся разработкой программного обеспечения. Мне задали вопрос о самой длинной уникальной подстроке в строке. Мои алгоритмы были следующими:

Начните с самого левого символа и сохраните символ в хеш-таблице с ключом как character и значением как index_where_it_last_occurred. Добавьте символ в строку ответа, пока его нет в хеш-таблице. Если мы снова столкнемся с сохраненным символом, я остановлю и запомню длину. Я очищаю хэш-таблицу, а затем начинаю снова с нужного индекса повторяющегося символа. Правильный индекс извлекается из флага (index_where_it_last_occurred). Если я когда-либо дойду до конца строки, я остановлюсь и вернусь к самой длинной длине.

Например, строка была, abcdecfg.

Я начинаю с a, хранить в хеш-таблице. Я магазин b и т.д. до e. Их индексы также хранятся. Когда я снова столкнулся с c, я останавливаюсь, так как он уже хэширован и записывает длину, равную 5. Я опустошаю хэш-таблицу и начинаю с правого индекса повторяющегося символа. Повторяющийся символ c, я начинаю снова с позиции 3, т. Е. Персонажа d. Я продолжаю делать это, пока не дойду до конца строки.

Мне интересно узнать, какая временная сложность этого алгоритма будет. ИМО, это будет O (n^2).

Это код.

import java.util.*; 
public class longest 
{ 
    static int longest_length = -1; 
    public static void main(String[] args) 
    { 
     Scanner in = new Scanner(System.in); 
     String str = in.nextLine(); 
     calc(str,0);  
     System.out.println(longest_length); 
    } 

    public static void calc(String str,int index) 
    { 
     if(index >= str.length()) return; 
     int temp_length = 0; 
     LinkedHashMap<Character,Integer> map = new LinkedHashMap<Character,Integer>(); 
     for (int i = index; i<str.length();i++) 
     { 
      if(!map.containsKey(str.charAt(i))) 
      { 
       map.put(str.charAt(i),i); 
       ++temp_length; 
      } 
      else if(map.containsKey(str.charAt(i))) 
      { 
       if(longest_length < temp_length) 
       { 
        longest_length = temp_length; 
       } 
       int last_index = map.get(str.charAt(i)); 
//    System.out.println(last_index); 
       calc(str,last_index+1); 
       break; 
      } 
     } 
     if(longest_length < temp_length) 
      longest_length = temp_length; 
    } 
} 

Answer 1

Если алфавит имеет размер K, то при перезагрузке подсчета вы прыгаете назад в большинстве K-1 место, поэтому вы читаете каждый символ строки в большинстве случаев K. Таким образом, алгоритм O (nK).

Входная строка, содержащая n/K копии алфавита, демонстрирует это наихудшее поведение. Например, если алфавит является {a, b, c}, строки вида "abcabcabc ... abc" обладают тем свойством, что почти каждый символ читается 3 раза вашим алгоритмом.

Вы можете решить исходную проблему в O (K + n) раз, используя пространство хранения O (K), используя динамическое программирование.

Пусть строка будет s, и мы сохраним номер M, который будет длиной максимальной строки unique_char, заканчивающейся на i, P, которая хранит там, где ранее был замечен каждый символ, и best, char string, найденный до сих пор.

Старт:

Set P[c] = -1 for each c in the alphabet. 
M = 0 
best = 0 

Тогда для каждого г:

M = min(M+1, i-P[s[i]]) 
best = max(best, M) 
P[s[i]] = i 

Это тривиально О (К) при хранении, и О (К + п) в рабочее время.