educative.io

Educative

Confused `windowStart = Math.max(windowStart, charIndexMap.get(rightChar) + 1);`

Is there any example to explain this part in solution? I’m not sure when the ‘windowStart’ will ahead of the last index of ‘rightChar’, I just use windowStart = charIndexMap.get(rightChar) + 1; and pass the test.

6 Likes

I also find this confusing. The explanation is not clear

2 Likes

Hi @Shanshan. Can you please share the lesson link?

To understand it better, take this example string: ‘abbac’.

First try with: windowStart = charIndexMap.get(rightChar) + 1;
See its result which comes as 4 and then run it with correct code.

2 Likes

Some official test cases should definitely be added for this tricky part…

I had the same confusion here- wouldn’t skipping the windowStart ahead break the sliding window pattern? But I think I understand now:

Example:
You have->
[zyab]bcada // maxLength = 4

next rightChar is “b” so we skip the map ahead to the first index of the duplicate letter “b” →
zya[b]bcada //maxLength = 4

This is ok because we just skip “ya” because we can know already that the shrinking window (1) can’t be bigger than we already had and (2) will be blocked on the right by the duplicate anyway so can’t grow.

If we’d just done a normal increment we would do->
z[yab]bcada
zy[ab]bcada
zya[b]bcada

Which ends up the same with more steps, and the maxLength remains 4 throughout.

1 Like