Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

here we have to find the longest substring which follows some constraints. let’s be a little greedy. we set starting position first index and go ahead. oh no, 😬 char at the current position is already seen. if we include this char in the segment then our segment doesn’t follow constraint.

one thought, set this position as a new starting position and go ahead but wait this is the first repeating char and any chars which are ahead of its last occurrence can be part of the new segment, and the new segment also in valid state.

observations , positions can be good or bad and when you reach to bad position here have to think 🤔 how we can update end points of segment.

paramters need to maintain — [ start, end, lastOcurrence, goal, update strategy ]

initially, the start and end of the segment are the first positions and when we go ahead, we will keep updating the end and putting its occurrence in a hash table.

update strategy — if i found an entry of current char in the hash table then have to move segment in a validated state. to achieve this, update the start point to its last occurrence. also, possible last occurrence of some char is outside the current segment just skip update.

you can also implement the approach using set in cpp .

Thanks for reading.