题目：求最长无重复子串
从一个字符串中找到一个连续子串，该子串中任何两个字符不能相同，求子串的最大长度并输出一条最长不重复子串。
输入: "abcdbefdhi"
输出: "befdhi" 6

思路

以如下字符串为例

abcdbefdhij

思路图

图中的start是一个标志位，表示当前不重复子串的起始位置，图中的数字表示记录字符出现位置的数组hash字典，比如字符b出现在第1位，那么hash_dic['b']=1。顺序扫描字符串，第4个位置时，在hashtable中发现b已经有记录，说明出现过（记出现的位置为k，此时k=1），那么当前的不重复子串长度 = 当前位置-start；下一个不重复子串就应该从第k+1个字符（2号位的c）开始，即令start = 2，并且把[start, k)位置的字符对应的hash字典清空（value置为-1），重新设置b在hash字典里的值为4。继续扫描直到再次发现相同的字符，和前面一样处理。特别注意全部处理完字符串，还要判断一下末尾的不重复子串是否是最长的。

代码（Python）

def cal(string):
    dic_hash={}
    start = 0
    res = 0
    arr =[]
    for index in range(0,len(string)):#初始化哈希字典
        dic_hash[string[index]]= -1;
    for index in range(0,len(string)):
        if dic_hash[string[index]] != -1:
            res = max(index-start,res)
            arr = string[start:index]
            last_start = start
            start = dic_hash[string[index]] + 1
            for j in range(last_start,dic_hash[string[index]]):#清空hash字典中start前面的部分
                dic_hash[string[j]] = -1
        dic_hash[string[index]] = index
    if max(res,len(string)-start)!= res:
        arr = string[start:len(string)]
        res = max(res,len(string)-start)

    return arr,res

时间复杂度：

考虑最坏的情况，由于使用了Hash字典, 每个元素访问不超过两次(添加与移除), 所以算法时间复杂度为O(n).[2]

References

[1]、 算法（十）-最长无重复字符子串

[2]、http://www.cnblogs.com/TenosDoIt/p/3736725.html
[3]、https://my.oschina.net/u/1047616/blog/494543