首页 > 试题广场 >

无重复字符最长子串

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

abcabcbb

输出

说明

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

示例2

输入

bbbbb

输出

说明

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

算法知识视频讲解

给我一个offer叭！！！

遍历
s=str(input())
tmp=list(s)
res=[]
count=[]
for i in range(len(tmp)):
    for j in range(i,len(tmp)):
        if tmp[j] not in res:
            res.append(tmp[j])
        else:
            break
    count.append(len(res))
    res=[]
print(max(count))

发表于 2020-03-16 14:16:26 回复(1)

pein531

使用双指针

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while((str = br.readLine()) != null)
            System.out.println(solve(str));
    }
    
    private static int solve(String s) {
        int left = 0, right = 0;
        int maxLen = 0;
        boolean[] used = new boolean[128];
        while(right < s.length()){
            if(!used[s.charAt(right)]){
                used[s.charAt(right)] = true;
                right ++;
            }else{
                maxLen = Math.max(maxLen, right - left);
                while(left < right && s.charAt(left) != s.charAt(right)){
                    used[s.charAt(left)] = false;
                    left ++;
                }
                left ++;
                right ++;
            }
        }
        maxLen = Math.max(maxLen, right - left);
        return maxLen;
    }
}

发表于 2020-10-18 18:50:25 回复(0)

JJJGGG

s = input()
sub = []
for i in range(len(s)):
    sub.append(s[i])
    for j in range(i+1,len(s)):
        if s[j] in set(sub[i]): break
        else: sub[i]+=s[j]
print(max(len(i) for i in sub))

发表于 2020-07-12 03:27:22 回复(0)

秃头一半

//主要思想：遍历整个字符串，将连续读取的存入map内，若发现有重复的字符出现则统计长度，
//进行下一轮的计数。
#include<bits/stdc++.h>
using namespace std;
int main(){
    char N[100000];
    gets(N);
    //存储已经读取的字符，在内循环进行判断，如果已经读入，则统计字符串长度
    //并进行下一轮的计数
    unordered_map<char,int> Map;
    int index,count,ans = 0;
    for(int i=0;i<strlen(N);){
         index = i;
         count = 0;
         while(Map[N[index]]!=1){
             Map[N[index]] = 1;
             index++;
             count++;
             //必须判断是否是结尾了，不然'\0'又会被算进来
             if(index>=strlen(N))
                 break;
         }
        if(count>ans)
            ans = count;
        i = index;
        Map.clear();
    }
    cout<<ans;
    return 0;
}

发表于 2020-04-10 12:50:18 回复(0)

求求给个offer。

def lengthOfLongestSubstring(s: str) -> int:
    left = 0
    cur_len = 0
    max_len = 0
    dict = set()
    for i in range(len(s)):
        cur_len += 1
        while s[i] in dict:
            dict.remove(s[left])
            cur_len -= 1
            left += 1
        if cur_len > max_len:
            max_len = cur_len
        dict.add(s[i])
        
    return max_len

s=str(input())
s=list(s)
print(lengthOfLongestSubstring(s))

发表于 2020-03-27 15:57:11 回复(0)

牛客255075616号

def judge(str):
    if len(str) == "":
        return 0
    letters = dict()
    res = 0
    start = 0
    for i in range(len(str)):
        if str[i] in letters and letters[str[i]]>=start:
            res = max(res, i-start)
            start = letters[str[i]]+1
        letters[str[i]] = i
    return res

发表于 2020-03-21 20:35:19 回复(0)

gywy

双指针思想

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 30;
int f[N];
int ans;

int main()
{
    string s;
    cin >> s;
    int i = 0;
    for (int j = 0; j < s.size(); j ++)
    {
        f[s[j] - 'a']++;
        while (i < j && f[s[j] - 'a'] > 1)
        {
            f[s[i] - 'a'] --;
            i ++;
        }
        ans = max(ans, j - i + 1);
    }
    cout << ans << endl;
    return 0;
}

编辑于 2020-03-15 21:28:43 回复(1)

阿金要努力

#include<iostream>
#include<unordered_map>
#include<string>
#include<algorithm>
using namespace std;
int lengthOfLongestSubstring(const string& s)
{
    int left=0, right=0, result=0;
    unordered_map<char, int> map;
    while(right<s.size())
    {
        map[s[right]]++;
        while(map[s[right]]>1)
        {
            map[s[left]]--;
            left++;
        }
        result=max(result, right-left+1);
        right++;
    }
    return result;
}
int main()
{
    string s;
    cin>>s;
    cout<<lengthOfLongestSubstring(s)<<endl;
    return 0;
}

发表于 2023-02-11 11:08:23 回复(0)

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)

年轻人不要搞窝里斗

s=input()
from collections import defaultdict
dic=defaultdict(lambda x:0)
 
dic[s[0]]=0
l=0
ret=0
for r in range(1,len(s)):
    if s[r] in dic and dic[s[r]]>=l:
        l=dic[s[r]]+1
    dic[s[r]]=r
    ret=max(ret,r-l+1)
print(ret)

力扣原题

发表于 2022-03-05 22:17:11 回复(0)

牛客740232263号

双指针

from collections import defaultdict

def process(s):
    if len(s) == 0:
        return 0
    smap = defaultdict(lambda: -1)
    l , r = 0, 0
    ans = 0
    while r < len(s):
        if smap[s[r]] >= l:
            l = smap[s[r]] + 1
        ans = max(ans, r - l + 1)
        smap[s[r]] = r
        r += 1
    return ans

if __name__ == '__main__':
    s = input()
    print(process(s))

发表于 2021-10-22 14:42:49 回复(0)

牛客627487021号

// O(n^2)的做法
#include <iostream>
#include <cstring>
#include <map>
using namespace std;

int main() {
    string orig;
    cin >> orig;
    
    std::map<char, int> bucket_map;
    int max_cnt = 0, cnt = 0;
    for (size_t i = 0; i < orig.size(); ++i) {
        bucket_map.clear();
        
        cnt = 0;
        for (size_t j = i + 1; j < orig.size(); ++j) {
            std::map<char, int>::iterator it = bucket_map.find(orig[j]);
            if (it != bucket_map.end() && it->second == 1) {
                if (cnt > max_cnt) {
                    max_cnt = cnt;
                }
                break;
            } else {
                bucket_map[orig[j]] = 1;
                cnt ++;
            }
        }
    }

    cout << max_cnt << endl;

    return 0;
}

编辑于 2021-03-15 15:34:36 回复(0)

人迹板桥霜

Brute Force

s = str(input())
tmp = set()
cnt = 0
cntl = []
for i in range(len(s)):
    if s[i] not in tmp:
        tmp.add(s[i])
        cnt += 1
    else:
        cntl.append(cnt)
        cnt = 0
        tmp.clear()
        tmp.add(s[i])
    
    if i == len(s)-1:
        cntl.append(cnt)

print(max(cntl)+1)

发表于 2020-10-20 11:13:10 回复(0)

ppdbz

a = list(input())
res = 0
l=r=0
for i in a:
    while i in a[r:l]:
        r += 1
    if l-r>res:
        res = l-r
    l += 1
print(res+1)

发表于 2020-09-05 17:38:08 回复(0)

牛客516100747号

是我对题目的理解出了问题吗

a = list(input())
b=[]
for i in a:
if not i in b:
b.append(i)
print(len(b))

编辑于 2020-08-19 13:02:46 回复(0)

牛客902271883号

一维数组动态规划

while True:
    try:
        string = input().strip()
        if string == '':
            print(0)
        else:
            res = 0
            dp = [1 for _ in range(len(string))]
            for i in range(1, len(string)):
                start = i - dp[i-1]
                if string[i] in string[start:i]:
                    pivot = 0
                    for j in range(i-1, -1, -1):
                        if string[j] == string[i]:
                            pivot = j
                            break
                    dp[i] = i - j
                else:
                    dp[i] = dp[i-1] + 1
                    if dp[i] > res:
                        res = dp[i]
            print(res)
    except:
        break

发表于 2020-08-03 20:09:07 回复(0)

过儿过过过

#include<iostream>
(720)#include<string>
#include<map>
(747)#include<algorithm>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int len;
	map<char,int> m;
	len=s.size();
	int n=0;
	int a[len];
    for(int i=0;i<len;i++)
    {
    	if(m.count(s[i])==0)
    	{
    		m[s[i]]++;
            if(m.size()>n)
			{
				n=m.size();
			 }    		
		}else
		{
			if(m.size()>n)
			{
				n=m.size();
			 } 
		    m.clear();
             m[s[i]]++;
		}
	}
	cout<<n;
	return 0;
}

拙见。

发表于 2020-04-09 12:52:15 回复(0)

heimingsheng

s = input()
jihe = []
max_len = 0
index = 0
for i in range(len(s)):
if s[i] not in jihe:
jihe.append(s[i])
if len(jihe) > max_len:
max_len = len(jihe)
else:
for j in range(index,i):
if s[j] != s[i]:
jihe.remove(s[j])
else:
index = j + 1
break
print(max_len)

发表于 2020-04-02 12:52:07 回复(0)

1Taoshen1

动态规划方法


	
#include <iostream>
#include <string>

using namespace std;

int longestsubstringwithoutduplication(const string& s)
{
	int *count = new int[26]; //统计每种字符上一次出现的位置
	for(int i=0;i<26;i++) count[i] = -1;  //初始化数组
	
	int sum = 0;  //统计长度的最大值 
	int preindex; //当前元素的上一次出现位置 
	int curlength = 0, maxlength = 0;  //当前子串长度和最大子串长度 
	for(int i=0;i<s.size();i++) 
	{
		preindex = count[s[i]-'a'];
		if(preindex < 0 || i - preindex > curlength)  curlength++;
		else{  //表示此子串结束 
			if(curlength > maxlength)  maxlength = curlength;
			curlength = i - preindex;
		}
		count[s[i]-'a'] = i;
	}
	if(curlength > maxlength)  maxlength = curlength;
	delete []count;
	return maxlength;
}

int main(void)
{
	string str;
	cin >> str;
	cout << longestsubstringwithoutduplication(str) << endl;
	return 0;
}

编辑于 2020-03-23 21:34:08 回复(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)

提交观点

问题信息

快手算法工程师 2020

上传者：小小

难度：

23条回答 38收藏 5187浏览

通过挑战的用户

阿金要努力

2023-02-11 11:08:06
调皮的火龙果在学习

2023-02-04 22:38:14
追击者732

2022-10-12 17:54:07
可爱抱抱呀😥

2022-10-04 21:19:41
yf胡

2022-09-28 16:01:05

无重复字符最长子串

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题