- 最长重复子串（返回最大长度）
- 395. 每个字符至少重复 K 次的最长子串（Medium）/ 424. 最多替换 K 次后的最长重复子串（Medium）/ （非）重复串问题！！！
![]()
【题目链接】
- 最长不含重复字符的子字符串（动态规划 / 双指针 + 哈希表，清晰图解）
![]()
![]()
![]()
![]()
代码
classSolution:### 1104 动态规划 + 哈希表 O(N)（64 ms，13.4 MB）deflengthOfLongestSubstring(self,s:str)->int:dic,res,tmp={},0,0# tmp表示前一时刻最长不含重复字符的子字符串的长度，初始化为0forjinrange(len(s)):# 遍历字符串中每一个字符i=dic.get(s[j],-1)# 获取下标idic[s[j]]=j# 更新某个字符s[j]出现的最新位置j（下标），更新哈希表tmp=tmp+1iftmp<j-ielsej-i# dp[j - 1] -> dp[j]res=max(res,tmp)# 更新最大值returnres### 1104 动态规划 + 线性查找 O(N2)（484 ms，13.6 MB）deflengthOfLongestSubstring(self,s:str)->int:res=tmp=0# tmp表示前一时刻最长不含重复字符的子字符串的长度，初始化为0forjinrange(len(s)):# 遍历字符串中每一个字符i=j-1# 初始化下标i，将i初始化为j左边的值whilei>=0ands[i]!=s[j]:i-=1# 从右往左更新i（逆序）tmp=tmp+1iftmp<j-ielsej-i# dp[j - 1] -> dp[j]res=max(res,tmp)# 更新最大值returnres### 1104 动态规划 + 双指针 O(N)（68 ms，13.6 MB）deflengthOfLongestSubstring(self,s:str)->int:dic,res,i={},0,-1# 初始化左指针i为-1forjinrange(len(s)):# 遍历字符串中每一个字符ifs[j]indic:# 检查当前字符是否在哈希表中i=max(dic[s[j]],i)# 若存在，则更新左指针idic[s[j]]=j# 更新某个字符s[j]出现的最新位置j（下标），更新哈希表res=max(res,j-i)# 更新最大值returnres
- 返回最长无重复字符的子串（【对应上面方法3：双指针】直接用这个，同时返回子字符串和长度，2026.4）
# 双指针classSolution:deflengthOfLongestSubstring(self,s):max_len=0max_sub=""ifnots:returnmax_sub,max_len# 滑动窗口：使用左指针 left 和右指针 right 维护一个窗口，窗口内字符都不重复left=0# 哈希表（集合）：char_set 记录当前窗口中的字符，用于快速判断重复char_set=set()forrightinrange(len(s)):# 若当前字符已经在窗口内，移动左指针直到重复字符被移出whiles[right]inchar_set:char_set.remove(s[left])left+=1# 将当前字符加入窗口char_set.add(s[right])curr_len=right-left+1# 更新结果：每次窗口合法后，计算当前长度，# 若大于已记录的最大长度，则更新最大长度和对应的子串ifcurr_len>max_len:max_len=curr_len max_sub=s[left:right+1]# print(f"长度: {max_len}, 子串: '{max_sub}'")returnmax_sub,max_len
1044. 最长重复子串（返回任一子串）
![]()
classSolution:deflongestDupSubstring(self,s:str)->str:ans=''max_len,start,end,n=0,0,1,len(s)# 每次看s[start:end]在之后s[start+1:]是否也出现，因为在s[start:]肯定出现一次，所以总共出现次数>=2# 出现的话，更新max_len,同时end后移，看更长的是否满足# 不出现的话，表明以start开头的子串不可能出现>=2次，start后移whileend<n:ifs[start:end]ins[start+1:]:# 判断子串出现至少两次# 如果子串长度超过当前最大值，更新最大值和ansifmax_len<end-start:max_len=end-start ans=s[start:end]end+=1continuestart+=1returnans
