最长不重复子串

问题描述：

　　给定一个字符串，求他的最长的不重复的子串

输入：

“absdsa”

输出：

“absd”

算法思想：

利用动态规划算法和hash表（在python中用字典保存）。首先定义两个变量，walker 和runner,当runner run到一个与之前重复的值的时候，此时runner就要停下来，先判断当前的walker和与runner相同的字符的位置，谁更大，如果后者更大的话，就对walker进行赋值，此时runner与walker之前的字符肯定是不相同的。这时候再进行最长子串的比较

它的python实现

class substring(object):
    def longestsubstring(self, s):
        walker = runner = 0
        length = len(s)
        dict = {}
        maxlength = 0
        while runner != length:
            if s[runner] in dict and walker <= dict[s[runner]]:
                walker = dict[s[runner]] +1
            else:
                   maxlength = max(maxlength, runner - walker +1)
            dict[s[runner]] = runner
            runner += 1
        return maxlength