# 3. Longest Substring Without Repeating Characters

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

Example 1:

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

Example 2:

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

Example 3:

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

# Solution

Approach 1: Brute force.

Approach 2: Sliding window with a set by moving the head pointer one step a time.

Approach 3: Sliding window with a map by moving the head pointer bypassing the repeated element.

# Code (Python)

Approach 2:

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        result = 1
        letters_in_window = set()
        left = 0
        for right in range(len(s)):
            if s[right] not in letters_in_window:
                letters_in_window.add(s[right])
            else:
                while s[left] != s[right]:
                    letters_in_window.remove(s[left])
                    left += 1
                left += 1
                letters_in_window.add(s[right])
            result = max(result, right - left + 1)
        return result

Approach 3:

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        result = 1
        latest_positions = {s[0]: 0}
        left = 0
        for right in range(1, len(s)):
            if s[right] not in latest_positions or latest_positions[s[right]] < left:
                latest_positions[s[right]] = right
            else:
                left = latest_positions[s[right]] + 1
                latest_positions[s[right]] = right
            result = max(result, right - left + 1)
        return result

# Code (C++)

Approach 2:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int head = 0;
        int tail = 0;
        int maxLen = 0;
        unordered_set<char> visited;
        while (head < n && tail < n)
        {
            if (visited.find(s[tail]) != visited.end())
            {
                visited.erase(s[head]);
                head++;
            }
            else
            {
                visited.insert(s[tail]);
                tail++;
                maxLen = (tail - head > maxLen) ? tail - head : maxLen;
            }
        }
        return maxLen;
    }
};

Approach 3:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int head = 0;
        int tail = 0;
        int maxLen = 0;
        unordered_map<char,int> visited;
        while (head < n && tail < n)
        {
            if (visited.find(s[tail]) != visited.end() && visited[s[tail]] >= head) //! 
            {
                head = visited[s[tail]] + 1;
            }
            visited[s[tail]] = tail;
            tail++;
            if (tail - head > maxLen)
                maxLen = tail - head;
        }
        return maxLen;
    }
};