首页 > 试题广场 >

查找无重复最长子串

[编程题]查找无重复最长子串

热度指数：6031 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：输入的字符串长度满足 $1 \le n \le 10^5 \$ ，字符串中仅包含小写的英文字母

输入描述:

输入类型为字符串，例如”abcde“

输出描述:

输出类型为整型， 例如 5

示例1

输入

pwwkew

输出

说明

无重复字符的最长子串是"kew"，其长度为 3

算法知识视频讲解

Polestar_a

类似于动态规划，每次的结果都和上一次的结果相关

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))

编辑于 2019-08-08 23:23:49 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s,res="";
    cin>>s;
    unordered_map<char, int> h;
    int max = 0,j=0,i=0;     
    while(i<s.size()&&j<s.size())
    {
        if(h[s[j]]==0)
        {
            h[s[j]]=1;
            j++;
            if(max<=(j-i))
                max=j-i;
        }
        else
        {
            h[s[i]]=0;
            i++;
        }
    }     
    cout<<max<<endl;
    return 0;
}

发表于 2019-07-13 19:09:50 回复(1)

小蝌蚪666

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
    int start = 0, maximum = 0;
    vector<int> hash(256, -1);
    string s;
    cin>>s;
    for(int i = 0; i < s.length(); ++i){
        if(hash[s[i]] == -1){
            maximum = max(i-start+1, maximum);
        }else{
            start = max(hash[s[i]]+1, start);
        }
        hash[s[i]] = i;
    }
    cout<<maximum<<endl;
    return 0;
}

最长不重复子串问题

变量：

start表示当前不重复子串的起始位置，初始化为0

maximum表示全局的最大不重复子串长度

数组hash表示字符出现的位置，全部初始化为-1表示没有出现过

算法：

遍历字符串，当前字符没有出现过，i-start+1得到不重复子串长度，和maximum比较取较大值

当前字符出现过，start需要往后挪，这分成两种情况：

1. 当前出现过的字符上一次出现的位置在start之前，此时start不用动

2. 当前出现过的字符上一次出现的位置在start之后，此时start挪到该位置的下一个位置，这时不重复子串长度一定小于等于上一次计算的值，不用更新maximum

每次都需要更新最新的字符出现位置:hash[s[i]] = i

发表于 2019-08-20 20:03:48 回复(0)

又笨又懒不想上课

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        System.out.println(new Solution().search(s));
        in.close();
    }
    
}
class Solution{
    public int search(String s) {
        int res = 1;
        char[] chs = s.toCharArray();
        for(int i = 0; i < chs.length; i++) {
            for(int j = i + 1; j < chs.length; j++) {
                int flag = 0;
                String temp = s.substring(i,j + 1);
                char[] chs1 = temp.toCharArray();
                for(int k = 0; k < temp.length(); k++) {
                    if(temp.indexOf(chs1[k]) != temp.lastIndexOf(chs1[k])) {
                        flag = 1;
                        break;
                    }
                }
                if(flag == 1) break;
                res = Math.max(res,temp.length());
            }
        }
        return res;
    }
}

发表于 2021-06-01 10:38:30 回复(0)

Java

lmz9509

/*
利用一个ArrayList或者set来保存
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));
        String str = br.readLine();
        int maxcount = Integer.MIN_VALUE;
        for(int i = 0;i<str.length();i++){
            ArrayList<String> arr = new ArrayList<String>();
            for(int j = i;j<str.length();j++){
                String s = String.valueOf(str.charAt(j));
                if(!arr.contains(s)){
                    arr.add(s);
                    if(arr.size()>maxcount)
                        maxcount = arr.size();
                }else{
                    break;
                }
            }
        }
        System.out.println(maxcount);
    }
}

发表于 2020-05-05 16:29:57 回复(0)

abcdFive

双指针

s = input()
low = 0
fast = 1
max_ = 0
while low < len(s) and fast < len(s):
    if s[fast] not in s[low:fast]:
        fast += 1
        max_ = max(max_,fast-low)
    else:
        low += 1
print(str(max_))

发表于 2020-03-23 16:02:48 回复(0)

初心者托奇

a,m = input(),[0,1]
while sum(m) < len(a) + 1:
    m[1 if len(set(a[m[0]:sum(m)])) == m[1] else 0] += 1
print(m[1] - 1)

编辑于 2020-03-19 12:50:39 回复(0)

C/C++

卷积神经网络哦

题目给提示了哈希用数组作为哈希即可

每个字符的ASCII码作为数组的下标，数组里放的是该字符在字符串中的位置

扫一遍即可，left是字符串的起点下标，如果某个字符已经有了，则将left位置更新为该字符后面一位。

然后每次更新一下最大长度

#include<bits/stdc++.h>
using namespace std;
int ha[256];

int main() {
    string s; cin>>s;
    memset(ha, -1, sizeof(ha));
    int left = 0, res = 0;
    for(int i = 0; i < s.length(); i++) {
        if(ha[s[i]] == -1) res = max(res, i-left+1);
        else left = ha[s[i]] + 1;
	    ha[s[i]] = i;
    }
    cout<<res<<endl;
}

编辑于 2019-12-27 10:43:49 回复(0)

C/C++

昔遥暮云

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    int Max=0;
    vector<int> dp(str.size(),0);
    dp[0]=1;
    for(int i=1,j=0;i<str.size();i++){
        int k;
        for(k=j;k<i;k++){
           if(str[k]==str[i]){
               dp[i]=1;
               j=i;
               break;
           }
        }
        if(k==i)
            dp[i]=dp[i-1]+1;
        Max=max(Max,dp[i]);
    }
    cout<<Max;
}

发表于 2019-10-08 19:58:19 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    int l = s.length(), Max=1, t;
    for(int i=0;i<l;i++){
        map<char,bool> b;
        int t = 0;
        for(int j=0;j<l-i;j++){
            char c = s[i+j];
            if(b.find(c)==b.end()){
                b[c] = true;
                t++; 
            }else{
                i += j-1;
                break;
            }
        }
        if(Max<t)
            Max = t;
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2019-09-07 11:18:55 回复(0)

C/C++

编译小伙

#include <iostream>
#include <string>
using namespace std;
 
int main(){
    string s;
    cin>>s;
    if(s.empty()) cout<<0<<endl;
    chart = s[0];
    char start = t;
    int len = 1,maxlen = 1,start_pos = 0;
    for(int i = 1;i < s.size();++i){
        //寻找不重复子串，不包括aaaaa这样的
        if(t != s[i] && start != s[i] ){
            t = s[i];
            len++;
        }
        else{
            //如果是aaaaa这样的
            if(start_pos + 1 == i){
                t = s[i];
                start_pos++;
                continue;
            }
            //其它情况
            else{
                if(i +1 < s.size()){
                    t = s[++i];
                    start = s[i];
                    start_pos = i;
                }
                len = 1;
                continue;
            }
        }
        //保存最长子串
        if(maxlen < len) maxlen = len;
    }
    cout <<maxlen<<endl;
    return 0;
      
}

编辑于 2019-07-15 16:57:35 回复(0)

哗~啦~啦

本人觉得这个应该是最好理解的：

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner in=new Scanner(System.in);
        String s=in.nextLine();
        System.out.println(Len(s));
    }
    public static int Len(String s){
        if(s.length()==0){
            return 0;
        }
        int max=0;
        int from=0;
        for(int i=0;i<s.length();i++){
            for(int j=from;j<i;j++){
                if(s.charAt(i)==s.charAt(j)){
                    from=j+1;
                }
            }
            if(i+1-from>max){
                max=i+1-from;
            }
        }
        return max;
    }
}

发表于 2019-07-29 11:12:35 回复(2)

Java

何止hz

滑动窗口

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
 * @Author: coderjjp
 * @Date: 2020-05-10 9:33
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int i = 0;
        for (; i < s.length(); i++){
            if (map.containsKey(s.charAt(i))){
                max = Math.max(max, i - left);
                left = Math.max(left, map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i), i);
        }
        System.out.println(Math.max(max, i - left));
    }
}

发表于 2020-05-11 09:41:55 回复(0)

牛客972605593号

from collections import defaultdict

class Solution:

def lengthOfLongestSubstring(self, s):

ans = left = 0

cnt = defaultdict(int) # 维护从下标 left 到下标 right 的字符及其出现次数

for right, c in enumerate(s):

cnt[c] += 1

while cnt[c] > 1: # 窗口内有重复字母

cnt[s[left]] -= 1 # 移除窗口左端点字母

left += 1 # 缩小窗口

ans = max(ans, right - left + 1) # 更新窗口长度最大值

return ans

if __name__ == '__main__':

s1 = input()

solution = Solution()

k = solution.lengthOfLongestSubstring(s1)

print(k)

发表于 2025-05-25 14:41:48 回复(0)

Python3

TS9527

经典双指针，左指针移动就行了，每次移动到当前字符上一次出现位置的下一个（记得取最大）

class MainActivity:

    def main(self):
        # Read the data
        s = input()
        # Initialization
        leftPtr = 0
        result = 1
        records = dict()
        # Traverse
        for rightPtr, char in enumerate(s):
            if char in records:
                leftPtr = max(leftPtr, records[char] + 1)
            records[char] = rightPtr
            result = max(result, rightPtr - leftPtr + 1)
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-24 16:17:49 回复(0)

牛客177594663号

import java.util.Scanner;

import java.util.Set;

import java.util.HashSet;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextLine()) { // 注意 while 处理多个 case

String line = in.nextLine();

try {

StringBuffer s = new StringBuffer();

StringBuffer currentMax = new StringBuffer();

StringBuffer sTmp = new StringBuffer();

Set<Character> set = new HashSet<Character>();

for (int i = 0; i < line.length(); i++) {

if (set.contains(line.charAt(i))) {

if (s.length() > currentMax.length()) {

currentMax.delete(0, currentMax.length());

currentMax.append(s);

}

sTmp.append(s.substring(s.indexOf(String.valueOf(line.charAt(i))) + 1));

s.delete(0, s.length());

s.append(sTmp);

sTmp.delete(0, sTmp.length());

set.remove(line.charAt(i));

}

s.append(line.charAt(i));

set.add(line.charAt(i));

}

System.out.print(s.length() > currentMax.length() ? s.length() : currentMax.length());

} catch (Exception e) {

}

发表于 2023-05-02 17:23:06 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var s string
    fmt.Fscan(in,&s)
    cnt:=map[byte]int{}
    ans:=0
    for l,r:=0,0;r<len(s);r++{
        cnt[s[r]]++
        for cnt[s[r]]>1&&l<r{
            cnt[s[l]]--
            if cnt[s[l]]==0{
                delete(cnt,s[l])
            }
            l++
        }
        if len(cnt)>ans{
            ans=len(cnt)
        }
    }
    fmt.Print(ans)
}

发表于 2023-03-22 01:11:11 回复(0)

C++

牛客409434554号

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;cin>>s;
    s.push_back(s.back());
    int a[123]={0},sum=0,maxn=INT_MIN;
    for(int i=0;i<s.length();i++)
    {
        for(int j=i;j<s.length()-1;j++)
        if(a[s[j]]==0)    {sum++;a[s[j]]=1;}
        else {maxn=max(maxn,sum);memset(a, 0, sizeof(a));sum=0;break;}
    }
    cout<<maxn;

数据量足够小，而且内循环最多26，直接暴力，不用判断每次字符的起始位置。

发表于 2022-01-22 03:17:33 回复(0)

牛客565112175号

有个用例错了，一直跑也过不了

发表于 2022-01-12 23:18:16 回复(0)

Python 3

牛客319205937号

s = input()
stack = []
i = 0
res = ''
while i < len(s):
    if s[i] not in res:
        res+=s[i]
    else:
        stack.append(res)
        res = s[i]
    i+=1
if len(res)!=0:
    stack.append(res)
print(len(max(stack, key=len)))

发表于 2021-07-23 22:38:16 回复(0)