performance - Finding the longest sub-string with no repetition in a string. Time Complexity? -

performance - Finding the longest sub-string with no repetition in a string. Time Complexity? -

i interviewed company software engineering science position. asked question of longest unique sub-string in string. algorithms follows -

start left-most character, , maintain storing character in hash table key character , value index_where_it_last_occurred. add together character reply string long not nowadays in hash table. if encounter stored character again, stop , note downwards length. empty hash table , start 1 time again right index of repeated character. right index retrieved (index_where_it_last_occurred) flag. if ever reach end of string, stop , homecoming longest length.

for example, string was, abcdecfg.

i start a, store in hash table. store b , on till e. indexes stored well. when encounter c again, stop since it's hashed , note downwards length 5. empty hash table, , start 1 time again right index of repeated character. repeated character beingness c, start 1 time again position 3 ie., character d. maintain doing while don't reach end of string.

i interested in knowing time complexity of algorithm be. imo, it'll o(n^2).

this code.

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>(); (int = 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; } }

if alphabet of size k, when restart counting jump @ k-1 places, read each character of string @ k times. algorithm o(nk).

the input string contains n/k copies of alphabet exhibits worst-case behavior. illustration if alphabet {a, b, c}, strings of form "abcabcabc...abc" have property every character read 3 times algorithm.

you can solve original problem in o(k+n) time, using o(k) storage space using dynamic programming.

let string s, , we'll maintain number m the length of maximum unique_char string ending @ i, p, stores each character seen, , best, longest unique-char string found far.

start:

set p[c] = -1 each c in alphabet. m = 0 best = 0

then, each i:

m = min(m+1, i-p[s[i]]) best = max(best, m) p[s[i]] =

this trivially o(k) in storage, , o(k+n) in running time.

performance algorithm time