educative.io

Educative

Window_start = max(window_start, char_index_map[right_char] + 1)?

I don’t understand why this line is needed in the python solution?

window_start = max(window_start, char_index_map[right_char] + 1)

We never advance start outside of this so it works just as well to use:
window_start = window_end

But then we don’t need the index of the character so we don’t need a hashmap. Why not just do this:

def non_repeat_substring(str1):
  window_start = 0 
  max_length = 0
  chars = set()

  for window_end in range(len(str1)): 
    right_char = str1[window_end] 
    if right_char in chars: 
      window_start = window_end
      
    chars.add(right_char)

    max_length = max(max_length, window_end - window_start + 1) 



  return max_length
1 Like

No it doesn’t actually. windowStart = windowEnd would ignore some non sequentially duplicate letters. Test the scenario below

“cbcad”

You are correct, @Renan_Geudes_da_Silv, but your test case is not showcasing the problem: the result is the same for both implementations.

Here’s a good test case: "abcadcbefg".
With windowStart = max(windowStart, charIndexMap[rightChar] + 1, it returns 7.
With windowStart = charIndexMap[rightChar] + 1, it returns 8.

1 Like

agree to @Claudiu
test case “abcadcbefg” is necessary here for the explanation of

window_start = max(window_start, char_index_map[right_char] + 1)
1 Like