查找无重复最长子串

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

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

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

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

输入描述:

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

输出描述:

输出类型为整型， 例如 5

示例1

输入

pwwkew

输出

说明

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

算法知识视频讲解

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)

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)