首页 > 试题广场 >

最长不含重复字符的子字符串

[编程题]最长不含重复字符的子字符串
  • 热度指数：54794 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
数据范围:

示例1

输入

"abcabcbb"

输出

3

说明

因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例2

输入

"bbbbb"

输出

1

说明

因为无重复字符的最长子串是"b"，所以其长度为 1。
示例3

输入

"pwwkew"

输出

3

说明

因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
算法知识视频讲解
添加回答
Python 3
牛客674947189号头像 牛客674947189号
class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        # write code here
        s=s.strip()
        k=len(s)
        str2=s[:1]
        len1,len2=1,1
        for i in range(1,k):
            if s[i] not in str2:
                len2=len2+1
                str2=str2+s[i]
                len1=max(len1,len2)
            else:
                len2=len(str2)-str2.index(s[i])
                str2=str2[str2.index(s[i])+1:]+s[i]
            
        return(len1)
        
发表于 2022-09-13 10:59:42 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    # 滑动窗口 + 哈希表
    def lengthOfLongestSubstring(self , s: str) -> int:
        mp = {}
        res = 0
        # 设置窗口左边界
        left = 0
        for right in range(len(s)):
            if s[right] in mp: mp[s[right]] += 1
            else: mp[s[right]] = 1
            # 窗口中有重复
            while mp[s[right]] > 1:
                mp[s[left]] -= 1
                left += 1
            # 维护子串长度最大值
            res = max(res, right - left + 1)
        return res
class Solution:
    # 双指针(时间换空间)
    def lengthOfLongestSubstring(self , s: str) -> int:
        cnt = 1
        l = 0
        r = 1
        while l < len(s) -1 and r < len(s):
            if s[r] not in s[l:r]:
                cnt = max(cnt, len(s[l:r+1]))
                r += 1
            else:
                l += 1
                r = l + 1
        return cnt
发表于 2022-05-08 21:29:30 回复(0)
Python 3
付付吖头像 付付吖
 d=[]
        count=0
        l=0
        r=0
        while r<len(s) :
            if s[r] not in d:
                d.append(s[r])
                r+=1
                count=max(count,r-l)
            else:
                d.pop(0)
                l+=1
        return count
发表于 2022-04-28 10:27:10 回复(0)
Python 3
kyzheng头像 kyzheng
双指针解法，耗时短，供参考 
class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        cnt = 1
        i = 0
        k = 1
        
        while i < len(s)-1 and k < len(s):
            if s[k] not in s[i: k]:
                cnt = max(cnt, len(s[i: k+1]))
                k += 1
            elif s[k] in s[i: k]:
                i += 1
                k = i+1
        
        return cnt


发表于 2022-03-28 11:02:43 回复(0)
Python 3
tanx2024头像 tanx2024
class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        # write code here
        dp = [1 for i in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                dp[i] = 1
            else:
                idx = s[i-dp[i-1]:i].rfind(s[i])
                if idx ==-1: 
                    dp[i] = dp[i-1]+1
                else:
                    dp[i] = dp[i-1]-(idx+1)+1
        return max(dp) 
发表于 2022-03-11 17:47:16 回复(0)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        # write code here
        if s==" ":
            return 1
        def cut_s(s,target):
            s=list(s)
            ind=s.index(target)
            s=s[ind+1:]+[target]
            return ''.join(s)
        res=[]
        string=''
        for i in s:
            if i not in string:
                string+=i
            else:
                res.append(len(string))
                string=cut_s(string, i)
        res.append(len(string))
        return max(res)

发表于 2022-01-28 12:06:16 回复(0)
Python 3
牛客925293305号头像 牛客925293305号 
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # write code here
        maxm, tmp, start = 0, 0, 0
        dic = dict()
        if len(s) <= 1:
            return len(s)
        for i in range(len(s)):
            if s[i] not in dic:
                dic[s[i]] = i
                tmp += 1
            else:
                if dic[s[i]] > start:
                    start = dic[s[i]]
                tmp = i - start
                dic[s[i]] = i
            if maxm < tmp:
                maxm = tmp
        return maxm

发表于 2021-12-06 17:41:59 回复(0)
Python 3
linqi4rea头像 linqi4rea
使用类似于求解最长回文子串的思路取走，复杂度超时 11/26组用例通过 
        n = len(s)
        for i in range(n, 0, -1):
            for j in range(0, n-i+1):
                if len(s[j:j+i]) == len(set(s[j:j+i])):
                    return len(s[j:j+i])
参考排行思路：多使用list的append 
a = []
        b, c = 0, 0
        for i in s:
            if i not in a:
                a.append(i)
                b += 1
            else:
                c = max(c, b)
                ind = a.index(i)
                a = a[(ind+1):]
                a.append(i) # ！！！！
                b = len(a)
        return max(b ,c)
发表于 2021-12-04 02:11:55 回复(0)
Python 3
阿司匹林Yo头像 阿司匹林Yo 
class Solution:
    def lengthOfLongestSubstring(self, s) -> int:
        if not str:
            return 0
        # tmp代表以第i-1个元素结尾的子串最大长度
        tmp, res = 1, 1
        # 记录每个字符最新出现的下标
        index = {s[0]: 0}
        for i in range(1, len(s)):
            if s[i] in index:
                tmp = tmp + 1 if i - index[s[i]] > tmp else (i - index[s[i]])
            else:
                tmp += 1

            index[s[i]] = i
            res = max(tmp, res)

        return res

发表于 2021-11-24 15:30:12 回复(0)
Python 3
牛客687764076号头像 牛客687764076号
class Solution:
    def lengthOfLongestSubstring(self , s: str) -> int:
        # write code here
        dp=[0 for i in range(len(s))]
        for i in range(len(s)):
            x=[]
            for j in range(i,len(s)):
                if s[j] not in x:
                    x.append(s[j])
                    dp[i]=dp[i]+1
                else:
                    break
        m=max(dp)
        return m
发表于 2021-11-10 19:41:29 回复(0)
提交观点

问题信息

字符串 哈希 双指针
难度：
11条回答 8251浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长不含重复字符的子字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号