3. Longest Substring Without Repeating Characters----LeetCode，

3. Longest Substring Without Repeating Characters----LeetCode，

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

题目翻译：给定一个字符串，找出最长的没有重复字符的子字符串，输出该字串长度。例如

“abcabcbb”    最长不重复字串是”abc“     返回长度： 3

”bbbbb“         最长不重复字串是”b“         返回长度： 1

解题思路：利用hash表

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxlen=0;
        int n=s.length();
        int *next = new int[n];
        int *first = new int[n+1];
        first[n]=n;
        int hash[256];
        memset(hash,n,sizeof(hash));
        for(int i=n-1;i>=0;i--){
            next[i]=hash[s[i]];
            hash[s[i]]=i;
            if(next[i]<first[i+1])
                first[i]=next[i];
            else
                first[i]=first[i+1];
        }
        for(int i=0;i<n;i++){
            if(first[i]-i>maxlen)
                maxlen=first[i]-i;
        }
        delete[]next;
        delete[]first;
        return maxlen;
    }
};

还有一种简单一些的解法，参考点击打开链接

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