HIPTSI- Longest Substring with non repeated characters

There are so many posts and YT videos out there on Leetcode problems, so I decided to do this differently. Here is my first post in the series "How I Plan To Solve It" - a series where, I describe how I plan on solving a Leetcode problem (but don't actually write any code for it)

https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

I'm not sure if this is the most efficient solution, but this is how I would initially start tackling this problem if I were to write code for it.

My thought process was

1. Start scanning the string
2. Find a substring with a non repeated character. This is my candidate
3. Try to find another substring that beats the size of the existing candidate
4. Continue until I have exhausted all characters in the string

Exhausting all possibilities, is where establishing an algorithm and writing a code is useful, especially if given a very large string.

I will need some sort of data structure, in this case I'm probably going to use a MAP, in order to remember if a character was seen prior, and the position at which it was seen

Scanning the string

While traversing the string, I keep track of each character and its position in the map. Starting at the left most character, I will traverse the string until I encounter a dupe.

At this point, I know 3 things

• Position of the previously seen character - the dupe
• Position where I started the traversal - the starting position
• And thanks to the map, the position where the character matching the dupe was first seen - the original dupe

With these three pieces of information I have my first candidate -

substring(startingPosition → dupePosition -1)

New Starting Position

Now, to find the next candidate. In order to do this I need a new starting position. It is safe to assume that I cannot start at any point prior to or including the original dupe. This is because the candidate at that starting position will almost certainly be smaller or equal to the candidate I just encountered (because of the dupe that we just matched on).

My new starting position should actually be one position past the original dupe.

originalDupePosition = map.get(dupeCharacter)

startPosition = originalDupePosition + 1

It will be important to remember that our map now contains characters and positions that are prior to the new starting position. We can either clean up the map, reset and rebuild, or add checks to ensure the code takes this into account.

Continue Traversing

At this point, I can be efficient and continue traversal from where I left off. After all, if I'm keeping track of the new starting position I can very easily get the new candidate via a substring function.

A dupe encounter means that I have a new candidate. This can be compared to the previous one and replaced if it is better

And now the cycle continues. Establish a new starting position and continue looking for better candidates until all characters in the string are exhausted, and we are left with a candidate that is the solution