3. Longest Substring Without Rep

最长不重复子串
Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

大致意思：给一个字符串，找到最长子串的长度，要求该子串不包含重复的字符。

常规解法：用哈希表来进行查找，这样查找效率会高些。从字符串头部开始计算子串，将没有重复出现的字符存入哈希表中，如果遇到相同的字符，表明当前不重复子串已经结束，记录此不重复子串的长度，并从哈希表中查到的该重复字符位置开始重新计算子串，比较确定此子串是否是当前最长的，遍历整个字符串后得到不重复字符的最长子串长度。

class Solution {
public:
   int lengthOfLongestSubstring(string s) {
       unordered_map<char, int> m;
       int maxLen = 0;
       int start = -1;
       
       for(int i=0; i<s.size(); i++) {
           auto it = m.find(s[i]);
           if((it != m.end()) && (it->second >= start)) {
               start = it->second;
           }
           m[s[i]] = i;
           maxLen = max(maxLen, i-start);
       }
       
       return maxLen;
   }
};

其他解法：上面用哈希表进行查询虽然相比常规查询要节省时间，但是我们还可以通过更简洁的方法来实现。我们可以用一种更巧妙的方法，因为一个字符占一个字节，八位，字符的ascii范围是在256范围内的，我们可以建立一个256大小的数组，每次字符的查询可以直接通过数组元素地址直接寻址，每一个数组元素的下标就是该字符的ascii值，该数组元素的值是该字符出现在字符串中的位置，每次遍历字符串中的字符，如果没出现重复则元素为默认值，累计字符串长度，如果出现重复则将元素值置为当前字符位置，并且重新计算长度，这样依次遍历完，计算出最长子串长度，时间复杂度会更低。

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