[LC] 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.
Time: O(N)
Space: O(N)

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

Solution 2:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        fast, slow, max_len = 0, 0, 0
        my_dict = {}
        for fast in range(len(s)):
            freq = my_dict.get(s[fast], 0)
            my_dict[s[fast]] = freq + 1
            if my_dict[s[fast]] > 1:
                while my_dict[s[fast]] > 1:
                    my_dict[s[slow]] -= 1
                    slow += 1
            else:
                my_dict[s[fast]] = 1
                max_len = max(max_len, fast - slow + 1)
        return max_len
        

Solution 3:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        my_dict = {}
        res = 0
        start, end, count = 0, 0, 0
        while end < len(s):
            end_char = s[end]
            end_freq = my_dict.get(end_char, 0)
            my_dict[end_char] = end_freq + 1
            if my_dict[end_char] > 1:
                count += 1
            end += 1
            
            while count > 0:
                start_char = s[start]
                start_freq = my_dict[start_char]
                my_dict[start_char] = start_freq - 1
                if my_dict[start_char] > 0:
                    count -= 1
                start += 1
            res = max(res, end - start)
        return res

Solution 4 (same with 1):

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int start = 0;
        int end = 0;
        int res = 0;
        while (end < s.length()) {
            if (set.contains(s.charAt(end))) {
                set.remove(s.charAt(start));
                start += 1;
            } else {
                set.add(s.charAt(end));
                end += 1;
                res = Math.max(res, end - start);
            }
        }
        return res;
    }
}

Solution 5:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start = 0, end = 0;
        int res = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (end < s.length()) {
            if (map.containsKey(s.charAt(end))) {
                start = Math.max(start, map.get(s.charAt(end)) + 1);
            }
            map.put(s.charAt(end), end);
            res = Math.max(res, end - start + 1);
            end += 1;
        }
        return res;
    }
}