博客

输入一个字符串（只包含 a~z 的字符），求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr，最长不含重复字符的子字符串为 acfr，长度为 4。

# 方法1：暴力法
#判断一个字符串是否重复
def repeatstring(str):
    for i in range(len(str)-1):
        for j in range(i+1,len(str)):
            if str[i]==str[j]:
                return True
    return False
# str='acfr'
# repeatstring(str)

#字符串列表里面最大长度字符串长度
def maxlilen(strli):
    max1=1
    for i in strli:
        if len(i)>max1:
            max1=len(i)
    return max1

def longsubstringwithoutduplication(str):
    #先找出所有的子字符串
    result=[]
    for i in range(len(str)):
        for j in range(i+1,len(str)+1):
            result.append(str[i:j])
    print(result)
    re=[]
    for i in result:
        if not repeatstring(i):
            re.append(i)
    for i in re:
        if len(i)==maxlilen(re):
            return i ,maxlilen(re)
        
            
str='arabcacfr'
longsubstringwithoutduplication(str)

#方法2：动态规划

#方法2：动态规划
def longsubstringwithoutduplication(str):
#     if not s:
#         return 0
#     curLength = 0
#     maxLength = 0
#     position = [-1]*256
#     for i in range(len(s)):
#         prevIndex = position[ord(s[i])]
#         if prevIndex < 0 or i-prevIndex>curLength:
#             curLength+=1
#         else:
#             if curLength>maxLength:
#                 maxLength = curLength
#             curLength = i-prevIndex
#         position[ord(s[i])]=i
#     if curLength>maxLength:
#         maxLength = curLength
#     return maxLength

    dic={str[0]:0}
    res=[1]
    for i in range(1,len(str)):
        if str[i] not in dic:
            res.append(res[i-1]+1)
        else:
            res.append(min(res[i-1]+1,i-dic[str[i]]))
        dic[str[i]]=i
    return max(res)    
            
str='arabcacfr'
longsubstringwithoutduplication(str)