题目描述
给定一个字符串，请找出其中长度最长且不含有重复字符的子串，计算该子串长度。
输入描述:
输入类型为字符串，例如”abcde“
输出描述:
输出类型为整型， 例如 5
示例1
输入：pwwkew
输出：3
说明：无重复字符的最长子串是"abc"，其长度为 3
这道题的解决方案是多种多样的，若下7种：
法1:利用Counter类,最简洁
from collections import Counter
print(len(Counter(list(input()))))
法2:数列去重
new_li=[]
for i in list(input()):
if i not in new_li:
new_li.append(i)
print(len(new_li))
法3：类似于动态规划，每次的结果都和上一次的结果相关
s = input()
dp =[1]*len(s)
for i in range(1,len(s)):
temp = s[i-dp[i-1]:i]
if s[i]not in temp:
dp[i]=dp[i-1]+1
else:
index = temp.index(s[i])
dp[i]= i-(index+i-dp[i-1])
print(max(dp))
法4:参考csdn的滑动窗口算法
def lengthOfLongestSubstring(data):
char_hash = {}
start,res = 0,0
for index,val in enumerate(data):
if val in char_hash and start <= char_hash[val]:
start = char_hash[val]+ 1
else:
res = max(res,index - start + 1)
char_hash[val]= index
return res
data = input()
print(lengthOfLongestSubstring(data))
法5：
s = list(input())
hashmap,l,ans = {},0,0
for i,c in enumerate(s):
if c in hashmap:
l = min(l + 1,i - hashmap[c])
else:
l += 1
hashmap[c]= i
ans = max(ans,l)
print(ans)
分两种情况
1. a...b...a...b, 假设这个字符串没有其他重复字母，那么在最后一个"b"之前，最长无重复子串为"...b...a..."，此时读到字符“b”，最长无重复子串变为"...a...b"或"b...a..."，即两个"b"之间的字符串（包含首或尾）
2. b...a...a...b，在最后一个"b"之前，最长无重复子串为"...a..."，此时读到字符"b"，最长无重复子串变为"...a...b"，即“...a...” + “b”.
综上，最长无重复子串的长度l = min(i - hashmap[s[i]], l + 1)
我们还需要记录global的最长无重复子串的长度，用另一个变量ans = max(ans, l)来记录即可.
法6：
s = list(input())
l =[]
res,cnt = 0,0
for i in range(len(s)):
if s[i]not in l:
l.append(s[i])
cnt += 1
res = max(cnt,res)
else:
n = l.index(s[i])
tmp_len = len(l)-n
l = s[i-tmp_len+1:i+1]
cnt = tmp_len
print(res)
法7：利用一个字典来保存当前出现的字符在字符串中的index,字符的集合小于ASCII码长度25
strs = input().strip()
maps =[-1 for i in range(257)]
ans = 0
start = 0
maps[ord(strs[0])]= 0
for i in range(1,len(strs)+ 1):
#遇到字符串结尾时，需要最后一次判断最长子串
if i == len(strs):
ans = max(ans,i - start)
break
#判断当前字符是否在maps中，如果不为默认值-1即代表在字符串下标i之前已经出现了该字符
elif maps[ord(strs[i])]!= -1:
#获取当前的最大字符串长度
ans = max(ans,i - start)
#从i之前重复字符串的下标的后一位开始，继续判断
start = maps[ord(strs[i])]+ 1
#修改当前字符出现的最新一个index
maps[ord(strs[i])]= i
# 返回最大字符串长度
print(ans)
网友评论