DayThree

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.

Thoughts:

window sliding, use two indexes(pointers) and slide over the string. Use a set to store all visited element and when iterating through the string, if current char has already been added to the set, it means we need to adjust starting point.

• Right implementation:

class Solution:
        """
        :type s: str
        :rtype: int
        """ 
    def lengthOfLongestSubstring(self, s):
        length = 0
        char_set = set()
        start = end = 0
        while start < len(s) and end < len(s):
            if s[end] in char_set:
                length = max(length, end - start)
                char_set.remove(s[start])
                start += 1
            else:
                char_set.add(s[end])
                end += 1
        return max(length, end - start)

• Wrong implementation, it is wrong because in the for loop "end = i", end should not be moving, because in this example "pwwwwfw", if end move to next index, we will remove wrong element from the set.
  So, for window sliding, always only moving one pointer, and keep the other one stay where it was until next time situation meets the condition of moving the pointer.

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """        
        if not s:
            return 0
        start = end = 0
        c_set = set()
        max_len = 0
        for i, v in enumerate(s):
            if v in c_set:
                max_len = max(max_len, i - start)
                c_set.remove(s[start])                                    
                start = start + 1      
            else:
                c_set.add(v)
            
        max_len = max(max_len, len(s) - start)
        return max_len

• Other good implementation from internet
  Use only one index to point the index where an element has a duplication in previous indexes
  "abcabc"[0, 1,2, 3, 4, 5], when index == 3, "a" has already appeared before (in index 0), set pointer = 3.
  Thinking about it this way, when you are looking for the longest substring without repeating chars, you are also looking for the longest substring that exists between two repeated characters.

class Solution:
        """
        :type s: str
        :rtype: int
        """ 
    def lengthOfLongestSubstring(self, s):
        max_length, start = 0, 0
        char_dict  =  {}
        for index, value in enumerate(s):
            if value in char_dict and char_dict[value] >= start:
                start = char_dict[value]
            char_dict[char] = index
            max_length = max(max_length, index - start)
        return max_length

C++ solution

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) {
            return 0;
        }
        int pointer = 0;
        int max_len = 0;
        unordered_map <int, int> char_dict;
        for(int i = 0; i<s.size(); i++){
           if(char_dict[s[i]] >= pointer){
               pointer = char_dict[s[i]];
           }
            char_dict[s[i]] = i;
            max_len = max(max_len, i - pointer);
        } 
        return max_len;
    }
};