无重复字符最长子串

[编程题]无重复字符最长子串

热度指数：1747 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

输入描述:

输入字符串(长度<=100000)

输出描述:

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

示例1

输入

abcabcbb

输出

说明

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

示例2

输入

bbbbb

输出

说明

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

算法知识视频讲解

Python

牛客318213606号

动态规划

def run(s):
    n=len(s)
    #dp[i]:s[0...i]中最长不重复子串的长度,i=0,1,...,n-1
    dp=[1 for _ in range(n)]

    dp[0]=1

    for i in range(1,n):
        p=-1
        for j in range(i-1,i-dp[i-1]-1,-1):
            if s[j]==s[i]:
                p=j#与s[i]重复字符所在下标j
                break

        # 如果当前字符未出现过
        if p==-1:
            dp[i]=dp[i-1]+1
        # 如果当前字符出现过
        else:
            dp[i]=i-p
    
    return max(dp)

while True:
    try:
        s=input()
        res=run(s)
        print(res)
    except:
        break

发表于 2022-06-27 21:47:50 回复(0)

Python

SWEDEN_offer

s = input()
if s == '':
    print(0)
else:
    stack = []
    num = 0
    stacknum = []
    for i in s:
        if i not in stack:
            stack.append(i)
            num += 1
        else:
            stacknum.append(num)
            num = 0
            stack = [i]
            num += 1
    stacknum.append(num)
    stacknum.sort()
    print(stacknum[-1])

发表于 2020-03-22 23:15:06 回复(0)