3 longest substring without repe
2017-10-19 本文已影响0人
Fei_JOB
1. sliding window: longest = end - start + 1;
cases need to cover:
"abcabcabcdd" contains repeated number
"abc" no repeated character: essentially return the length of the string.
for every end, we can get the longest substring ending with s.charAt(end), so using the hash array to record how many times the character appeared already. When (hash[endChar]) > 1, which means the current end is a repeated character, the start is not valid for this substring, we need to move start until hash[endChar] <= 1 again, then end - start + 1 is the length valid for current end.
scan along, when end reached the boundary, we got the longest length.