难度：中等
给定一个字符串，找出不含有重复字符的最长子串的长度。

输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。

输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。

输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。

最优解：声明一个数组用来标记所有字符上次出现的位置

Java实现：

public static int lengthOfLongestSubstring(String s) {
    int result = 0;//最终长度
    int distance = 0;//距离上次出现的索引距离
    int[] index = new int[128];
    for(int i=0;i<s.length();i++) {
        distance = Math.max(index[s.charAt(i)], distance);
        result = Math.max(result, i-distance+1);
        index[s.charAt(i)] = i+1;
    }
    return result;
}

解法一：逐一比较耗时较长

public int lengthOfLongestSubstring(String s) {
    int length = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int j = i+1; j <= s.length(); j++) {
            String str = s.substring(i, j);
            Set<Character> set = new HashSet<>();
            boolean exist = false;
            for(int k=i;k<j;k++) {
                if(set.contains(s.charAt(k))) {
                    exist = true;
                }
                set.add(s.charAt(k));
            }
            if(length<str.length()&&exist==false) {
                length = str.length();
            }
        }
    }
    return length;
}

解法二：逐义字符串比较判断拆分，组合新串，能够获取到最长子串，字符串过长会消耗很大的内存

public int lengthOfLongestSubstring(String s) {
    if(s.length()==0)return 0;
    String finalStr = "";
    String exsit = "";
    while(s.length()>0) {
        String str = s.substring(0, 1);
        s = s.substring(1);
        int index = exsit.indexOf(str);
        if(index==-1) {
            exsit +=str;
        }else {
            if(exsit.length()>finalStr.length()) {
                finalStr = exsit;
            }
            if(index<exsit.length()-1) {
                exsit = exsit.substring(index+1)+str;
            }else {
                exsit = str;
            }
        }
    }
    if(exsit.length()>finalStr.length()) {
        finalStr = exsit;
    }
    return finalStr.length();
}

C语言实现

int main(int argc, const char * argv[]) {
    char *s = "qwwdew";
    int length = lengthOfLongestSubstring(s);
    printf("%d\n",length);
    return 0;
}
int lengthOfLongestSubstring(char* s) {
    int length = 0;
    int distance = 0;
    int index[128] = {0};
    for(int i=0;i<strlen(s);i++){
        int char_index = (int)s[i];
        distance = index[char_index]>distance?index[char_index]:distance;
        length = (i-distance+1)>length?(i-distance+1):length;
        index[char_index] = i+1;
        
    }
    return length;
}