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, 1
        visited = set(s[slow])
            
        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