Longest String Without Repeating Characters

Question statment

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

Example:

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

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution

The idea is we need to keep counting until we find a duplication.

For example given this text:

abcabfdd

At second point a where we find a duplicate. We need to start counting from where there is no duplication anymore (b).

So:

   v
abcabfdd
 ^

Because at b, there is no duplication anymore. Similarly, when we find b as duplicated, we need to count from where there is no duplication, hence c:

    v
abcabfdd
  ^

Similarly, when reaching second d:

       v
abcabfdd
  ^

We need to count from when there is no duplication anymore: the same d

       v
abcabfdd
       ^

Implementation

As a result, we can see that we can keep track of a set. When seeing a duplication, we can just keep poping from the set until it's not duplicated anymore, for example:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) <= 1: return len(s)
        
        result = 0
        slow, fast = 0, 0
        visited = set()
            
        while (fast < len(s)):
            while s[fast] in visited:
                visited.remove(s[slow])
                slow += 1
            visited.add(s[fast])
            result = max(result, fast - slow + 1)
            fast += 1
        
        return result

Time complexity: $O(n*2)$

• Some elements need to visited twice for the visited to remove.
• But however it should not goes over $O(n^2)$ because worst case slow can go up to the current fast and the algorithm keeps running.
  Space complexity: $O(n)$
• We use a set to keep track of visited element

Optimisation

We can optimise our time complexity. It's obvious that we need to find a point at which there is no duplication anymore. As a result, we can start counting from the next character of the duplicated character's last appearance:

class App:
    def lengthOfLongestSubstring(self, s: str) -> int:
        letterToIndexMap = {}
        left, right = 0, 0

        maxLength = 0

        while (right < len(s)):
            currLetter = s[right]

            if currLetter in letterToIndexMap and letterToIndexMap[currLetter] + 1 > left:
                left = letterToIndexMap[currLetter] + 1

            maxLength = max(maxLength, right - left + 1)
            letterToIndexMap[currLetter] = right

            right += 1
        

        return maxLength

Time complexity: $O(n)$
Space complexity: $O(n)$

• We use a dict to keep track of visited element

[!note]
We need the condition that letterToIndexMap[currLetter] + 1 > left because without it the left pointer might move backwards. For our algorithm, we only allow it to move forward.

This will still work because if the appearance is somewhere behind left, if we're counting from left we shouldn't get that appearance.

[!important]
In here we always need to calculate maxLength = max(maxLength, right - left + 1) doesn't matter if the currLetter is in letterToIndexMap or not.

The reason is if we do something like if currLetter not in letterToIndexMap: then only calculate, we will miss conditions since we actually never remove visited letter from letterToIndexMap but only use left as the guideline