首页 > 试题广场 >

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

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

热度指数：47997 时间限制：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

唐氏儿来刷题

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

  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)

Java

风花雪月大头鬼

import java.util.*;


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

        for (int i = 1; i < dp.length; i++){
            dp[i] = 1;
//             if (map.containsKey(s.charAt(i-1))){
                dp[i] = Math.min(dp[i-1]+1, i-map.getOrDefault(s.charAt(i-1), 0));
//             }else {
//                 dp[i] = dp[i-1]+1;
//             }
            map.put(s.charAt(i-1), i);

            res = Math.max(res, dp[i]);

        }
        return res;
    }
}
这是我看了题解之后写出来的
为啥这个ifelse可以注释掉啊
我看了一下，不能理解dp[i] = Math.min(dp[i-1]+1, i-map.getOrDefault(s.charAt(i-1), 0));
为什么这里的dp[i-1]还要+1，不能理解

发表于 2022-05-06 19:33:28 回复(0)

Java

必进大厂的飞

    /**
     * 找到字符串中没有重复字符的最长字串
     * 步骤：
     * 1. 右指针一直右移
     * 2. 通过辅助空间判断右指针的元素是否出现过；
     * 3. 如果没出现过 添加进集合中 
     * 4. 如果出现过 通过一个while循环 左指针向左移 集合每次删除最左边的元素 直至不含该元素
     * 5. 每一次对右指针元素的操作过程都需要更新最大值
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring (String s) {
        // 左右指针
        int left = 0;
        int right = 0;
        int max = Integer.MIN_VALUE;
        ArrayList<Character> record = new ArrayList<>();
        // right一直移到最右边
        while (right < s.length()){
            // 有重复的left指针右移直至删除那个重复的值
            while (record.contains(s.charAt(right))){
                    // 每次删除第一个 而不是删除left ！！
                    record.remove(0);
                    // 每次删除一个left加一
                    left ++;
            }
            // 处理完right后统计长度
            record.add(s.charAt(right));
            right ++;
            if(right - left > max) max = right - left;
        }
        return max;
    }

发表于 2022-05-03 17:04:32 回复(0)

提交观点

问题信息

字符串哈希双指针

难度：

48条回答 483收藏 3842浏览

通过挑战的用户

查看代码

牛客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

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

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题