面试题48：最长不含重复字符的子字符串

题目：
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

思路：
这道题目需要用到动态规划的思想，定义函数f(i)为不含重复字符串的最长长度，当没有出现重复时，f(i) = f(i-1)+1；当出现重复的字符串时，两种情况：重复字符之间的距离d大于当前的curLen时，说明这个重复对于当前字符串没有影响，可以直接在f(i-1)基础上加1；否则说明当前的字符串已经出现重复，那么相应的curLen应该等于重复的字符串之间的距离。具体代码思路如下：

48 最长不含重复字符的子字符串.png

代码实现：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        #初始化变量
        curLen = 0
        maxLen = 0
        position ={}   #字典
        for i in range(len(s)):
            if s[i] not in position or curLen < i-position[s[i]]:  #如果没有重复或者距离大于                                                                     #curLen，直接加1即可
                curLen +=1
            else:
                curLen = i-position[s[i]]   #两个重复字符之间距离就是当前不重复字符串的长度
            position[s[i]] = i  #更新字符的位置
            if curLen > maxLen:
                maxLen = curLen
        return maxLen

提交结果：