首页 > 试题广场 >

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

[编程题]最长不含重复字符的子字符串

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

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

数据范围:

$\ \text{s.length}\le 40000$

示例1

输入

"abcabcbb"

输出

说明

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

示例2

输入

"bbbbb"

输出

说明

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

示例3

输入

"pwwkew"

输出

说明

因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

算法知识视频讲解

Java

牛客499848474号

用hashset甚至把子串求出来了😂

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        // write code here
        if(s == null){
            return 0;
        }
        Set<Character> distinct = new HashSet<>();
        int slow = 0;
        int fast = 0;
        int longest = 0;
        while (fast < s.length()) {
            if (distinct.contains(s.charAt(fast))) {
                distinct.remove(s.charAt(slow));
                slow++;
                //↑可合并为distinct.remove(s.charAt(slow++));
            } else {
                distinct.add(s.charAt(fast));
                fast++;
                //↑可合并为distinct.add(s.charAt(fast++));
                longest = Math.max(longest, fast - slow);
            }
        }
        return longest;
    }
}

发表于 2024-09-17 17:17:12 回复(0)

Java

୧⍢⃝୨

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();

        int res = 0;
        int i = 0;
        for (int j = 0; j < n; j++) {
            char ch1 = s.charAt(j);
            map.put(ch1, map.getOrDefault(ch1, 0) + 1);

            if (map.size() == j - i + 1) {
                res = Math.max(res, j - i + 1);
            }

            if (map.size() < j - i + 1) {
                char ch2 = s.charAt(i);
                map.put(ch2, map.get(ch2) - 1);
                if (map.get(ch2) == 0) {
                    map.remove(ch2);
                }
                i++;
            }
        }
        return res;

    }
}

发表于 2024-08-05 15:00:55 回复(0)

Java

唐氏综合征

正常思维的小白解法：双指针

  public int lengthOfLongestSubstring(String s) {
        // write code here
        // 典型的额双指针问题
        int len = s.length();
        if(len <= 1)
            return s.length();
        int maxLen = 0;
        ArrayList<Character> charList = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                char c = s.charAt(j);
                if(!charList.contains(c))
                    charList.add(c);
                else {
                    maxLen = Math.max(maxLen, charList.size());
                    charList.clear();
                    break;
                }
            }
        }
        return maxLen;
    }

大神解法，滑动窗口 + HASH 编码（ASCII码表），时间复杂度直接降低至 O(n)

 public int lengthOfLongestSubstring(String s) {
        // write code here
        int len = 0;
        int[] hash = new int[256];
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            hash[c]++; // 初始化时，每个元素对应 ASCII 的数字的值为 1
            while (hash[c] > 1) { // 发现有重复的字符串
                // 寻找重复元素的下一个下标，退出就是为 j
                hash[s.charAt(j)] --;
                j++;
            }
            // 当前的最大值
            len = Math.max(i - j + 1, len);
            // 继续往下寻找...
        }
        return len;
    }

发表于 2024-04-26 16:36:44 回复(0)

Java

鸭梨杉达

    public int lengthOfLongestSubstring (String s) {
        // write code here
        HashMap<Character, Integer> mp = new HashMap<>();
        int res = 0;
        if(s.length() <= 1){
            return s.length();
        }
        int left = 0, right = 0;
        while(right < s.length()){
            if(mp.containsKey(s.charAt(right))){
                mp.put(s.charAt(right), mp.get(s.charAt(right)) + 1);
            } else {
                mp.put(s.charAt(right), 1);
            }
            if(mp.get(s.charAt(right)) > 1){
                // 因为每次subring提取出来的字符串索引值都是从0开始，
                // 所以需要加上左边界left，才能表示s.charAT(right)字符在s中的索引位置
                int index = s.substring(left, right).indexOf(s.charAt(right)) + left;
                mp.put(s.charAt(right), mp.get(s.charAt(right))-1);  // 保证字符left,right区间的字符只出现一次。如果不做这一步，假设abcac,此时a重复了，在区间[0,4]之间，a出现两次，移动left到1时，a在[1,4]之间只出现一次，如果不-1，则还是两次，就会判定错误。
                res = Math.max(res, right - left);
                left = index + 1;
            }
            right++;
        }
        // 会出现一种情况，right一直到结束，都没有重复，此时就无法进入if条件判断长度
        // 需要在循环结束时，判断最后一个是否重复？ 重复，说明已经进入循环内的if判断过
        // 不重复，说明还需要再进行判断一次，判断res 与 当前right - left 长度
        return mp.get(s.charAt(right-1)) == 1 ? res = Math.max(res, right - left) : res;

发表于 2024-04-25 20:02:36 回复(0)

Java

码客明

public int lengthOfLongestSubstring (String s) {
        int left = 0;
        int right = 0;
        int max = 0;
        while(right<s.length()){
            while(s.substring(left,right).contains(s.charAt(right)+"")){
                left++;
            }
            if(max<right-left+1){
                max = right-left+1;
            }
            right++;
        }
        return max;
    }

发表于 2023-06-06 18:07:15 回复(0)

Java

^ǒ^月亮船^

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        //不重复最长字符串长度
        int maxCount = 0;
        //前指针
        int frontIndex = 0;
        //转成char数组
        char[] cs = s.toCharArray();
        //字重复判别数组
        int[] intArr = new int[256];
        //记录单次不重复最长字符串长度
        int count = 0;

        for (int i = 0; i < cs.length; i++) {
            
            if (intArr[cs[i]] >= 1) {
                //重置为0
                intArr = new int[256];
                if (maxCount < count) {
                    //获取不重复最长字符串长度
                    maxCount = count;
                }
                count = 0;
                //下标重新设置
                i = (frontIndex++);
            } else {
                //记录字符
                intArr[cs[i]]++;
                count++;
            }
        }

        return maxCount > count ? maxCount : count;
    }
}

发表于 2023-03-17 16:17:27 回复(0)

Java

Jycjmf

    public int lengthOfLongestSubstring (String s) {
        Set<Character> charSet = new HashSet<>();//感觉用set就足够了
        int res = 0;
        int left = 0, right = 0;
        for (; right < s.length(); right++) {
            while (charSet.contains(s.charAt(right))) {
                charSet.remove(s.charAt(left));
                left++;
            }
            charSet.add(s.charAt(right));
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

发表于 2022-11-12 09:29:48 回复(0)

Java

ludvig

import java.util.Arrays;

public class Solution {

public int lengthOfLongestSubstring (String s) {

int[] dp = new int[s.length()];

Arrays.fill(dp,1);

for (int i = 1; i < s.length(); i++) {

if(!s.substring(i-dp[i-1],i).contains(s.substring(i,i+1))){

dp[i] = dp[i-1]+1;

}else{

for (int j = i-dp[i-1]; j < i; j++) {

if(!s.substring(j,i).contains(s.substring(i,i+1))){

dp[i] = s.substring(j,i).length()+1;

break;

}

Arrays.sort(dp);

return dp[dp.length-1];

}

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

Java

牛客用户007

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        // write code here
        ArrayDeque<Character> queue = new ArrayDeque<>();
        int res = 0;
        for (int i = 0; i < s.length(); i ++) {
            if (queue.contains(s.charAt(i))) {
                while (queue.peek() != s.charAt(i)) {
                    queue.remove();
                }
                queue.remove();
            }
            queue.add(s.charAt(i));
            res = Math.max(res, queue.size());
        }
        return res;
    }
}

发表于 2022-09-14 11:40:01 回复(0)

Java

PenGuin！

滑动窗口+Hash表

public static int longestSubStringWithoutDuplication(String str) {
    Map<Character, Integer> map = new HashMap<>();
    int maxLen = 1;
    int mark = 0;//左边界
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (map.containsKey(c)) {
            mark = Math.max(mark, map.get(c) + 1);
        }
        map.put(c, i);
        maxLen = Math.max(maxLen, i - mark + 1);
    }
    return maxLen;
}

发表于 2022-09-13 23:09:53 回复(0)

Java

牛客208400313号

public int lengthOfLongestSubstring(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for (int i = 0; i < 128; i++) last[i] = -1;

        int start = 0;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i);
            // 控制窗口开始位置
            start = Math.max(start, last[index] + 1);
            // 判断哪个窗口更长
            res = Math.max(res, i - start + 1);
            // 记录出现位置
            last[index] = i;
        }

        return res;
    }

发表于 2022-08-17 18:04:05 回复(0)

Java

待凤惜变优秀

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        // write code here
        if(s.length() <= 1) return s.length();
        int[] arr = new int[100010];
        int res = 0;
        for(int i=0,j=0;i<s.length();i++){
            arr[s.charAt(i)]++;
            while(arr[s.charAt(i)] > 1){
                arr[s.charAt(j)]--;
                j++;
            }
            res = Math.max(res,i-j+1);
        }
        return res;
    }
}

发表于 2022-08-10 17:43:16 回复(0)

Java

GolinYoung

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        // write code here
        int res=0;
        for(int i=0;i<s.length();i++){
            int sum=1;
            for(int j=i+1;j<s.length();j++){
                if(s.substring(i,j).lastIndexOf(s.charAt(j)+"")>-1){
                    break;
                }
                sum++;
            }
            res=Math.max(res,sum);
        }
        return res;
    }
}

发表于 2022-07-28 22:39:21 回复(0)

Java

小周sama

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        // write code here
        int n = s.length();
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            int count = 0;
            Set<Character> set=  new HashSet<>();
            for(int j = i; j < n; j++){
                if(set.contains(s.charAt(j))){
                    break;
                }
                set.add(s.charAt(j));
                count++;
            }
            max = Math.max(count,max);
        }
        return max;
    }
}

发表于 2022-07-27 10:55:29 回复(0)

Java

NorthXwind

 public int lengthOfLongestSubstring (String s) {
        // write code here
        HashMap<Character, Integer> map = new HashMap<>();
        int res = 0;
        int l = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            } else {
                map.put(s.charAt(i), 1);
            }
            //重复了就一直移动左边界 直到不重复
            while (map.get(s.charAt(i)) > 1) {
                map.put(s.charAt(l), map.get(s.charAt(l)) - 1);
                l++;
            }
            res = Math.max(res, i - l + 1);
        }
        return res;
    }
}

发表于 2022-06-14 15:16:32 回复(0)

Java

饥饿的懒羊羊在刷题

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        // write code here
        Map<Character,Integer>map=new HashMap<>();
        int left=0,maxlength=0;
        for(int i=0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                left=Math.max(left,map.get(s.charAt(i))+1);
            }
            maxlength=Math.max(i-left+1,maxlength);
            map.put(s.charAt(i),i);
            
        }
        return maxlength;
    
    }
}

发表于 2022-06-12 17:54:12 回复(0)

Java

牛客小健健

       //双端队列
    public int lengthOfLongestSubstring (String s) {
        // write code here
        Deque<Character> queue = new ArrayDeque<>();
        int len = s.length();
        int ret = 0;
        for(int i=0; i<len; i++){
            char c = s.charAt(i);
            while(queue.contains(c)){
                queue.pollFirst();
            }
            queue.offerLast(c);
            ret = Math.max(ret, queue.size());
        }
        return ret;
    }

发表于 2022-06-10 16:18:43 回复(0)

Java

一川烟草平如剪

//不用多说

   public int lengthOfLongestSubstring (String s) {
        Queue<Character> list = new LinkedList<>();
        int max=0;
        for (char c : s.toCharArray()) {
            while (list.contains(c)){
                list.poll();
            }
            list.add(c);
            max=Math.max(max,list.size());
        }
        return max;

    }

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

提交观点

问题信息

字符串哈希双指针

难度：

50条回答 573收藏 8250浏览

通过挑战的用户

查看代码

牛客83949...

2023-03-07 00:30:48
Elastic...

2023-02-25 20:29:09
牛客58818...

2022-10-16 17:39:13
牛客58370...

2022-09-27 20:44:03
牛客46916...

2022-09-16 15:31:07

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

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题