leetcode3. Longest Substring Wit

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

Example 1:
---
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", which the length is 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.

Note:
---
保证好起始点的位置，确定好末尾；
利用hashmap的关键字唯一性；
c++主要要采用unordered_map，python采用dict,key值存放字母，value记录字母的序号。

// C++
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<int, int> num_map;        //hash table用来记录substring，便于之后查询字符字符是否重复
        int length = 0;     //用于记录最长substring长度
        int i = 0, j = 0;
        unordered_map<int, int>::iterator iter;
        while (i < s.length() - length && j < s.length())
        {
            iter = num_map.find(s[j]);      //判断目前存储的substring中是否存在重复字符
            if (iter == num_map.end())      //存在的话，则将该元素存储起来，并及时更新substring的长度
            {
                num_map[s[j]] = j;
                j++;
                if (length < (j - i)) length = j - i;
            }
            //如果迭代器遇到了重复字符,重复出现在哪里？从第i个元素开始检测
            //如果迭代器遇到了重复字符，那么说明从第i个元素开始的substring最大长度就是目前的length了,因此紧接着判断[i+1,j]的情况
            //j是不需要再从i+1开始的，因为我们只需将第i个元素擦除掉就可以了，这就是[i+1,j]中substring元素
            else            
            {
                num_map.erase(s[i]);
                i++;
            }
        }
        return length;
    }
};

# python
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        chars = dict()
        maxlen = 0
        start = 0
        for i,c in enumerate(s):
            if (c in chars) and (start <= chars[c]):
                start = chars[c]+1
            else:
                maxlen = max(i-start+1,maxlen)
            chars[c]=i

        return maxlen