3. Longest Substring Without Repeating Characters

------------------------------------------------------question-------------------------------------------------

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---------------------------------------------------

哈希表方法：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int>dict(256, -1);
        int start = -1, num = 0;
        for(int i=0; i!=s.length(); i++)
        {
            if(dict[s[i]]>start)
                start = dict[s[i]];
            dict[s[i]] = i;
            num = max(num, i-start);
        }
    return num;
    }       
};


-----------------------------------------------------analyse---------------------------------------------------

该解法巧妙地应用哈希表，利用数组来映射ASCII码中字符，然后字符出现一次表示记录记录该字符的位置，等到下次再出现就能算出子串长度并进行比较：
   首先方法内定义一个返回整形即字符串最长子串长度的函数。
   创建一个可变长数组，映射ASCII码表，数组中的值全部赋值为-1
   依次取字符，并进行判断dict[s[1]], 如果s[i]=a ,a 在ASCII码表中的值为61,那么相当于取dict[61]=-1. 没一个字符第一次出现时肯定都是-1，
于是就另dict[s[i]] = i，相当于在数组中对应a的那个位置记录为a第一次出现在字符串中的序号，当再一次出现a时，就会进入if内的语句，另start
为上次a出现的位置。通过当前的i-start就能得到一个不重复子串的长度，然后循环比较完得到最长子串长度。