3. 无重复字符的最长子串/面试题48. 最长不含重复字符的子字符串(简单)

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

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

思路1

动态规划思路

dp[j] 代表以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度。

设字符 s[j] 左边距离最近的相同字符为 s[i] ，即 s[i] = s[j]。

当 i < 0 ，即 s[j]左边无相同字符，则 dp[j] = dp[j-1] + 1 ；
当 dp[j - 1] < j - i ，说明字符 s[i]在子字符串 dp[j-1]区间之外 ，则 dp[j] = dp[j - 1] + 1 ；
当 dp[j−1]≥j−i ，说明字符 s[i]s[i] 在子字符串 dp[j-1]区间之中 ，则dp[j] 的左边界由 s[i] 决定，即 dp[j] = j - i；
$$
d p[j]=\left{\begin{array}{ll}
d p[j-1]+1 & , d p[j-1]<j-i \
j-i & , d p[j-1] \geq j-i
\end{array}\right.
$$

思路2

滑动窗口，实质性也是动态规划,未写

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {
        //一维dp，滑动窗口,dp表示以i字符为结尾的最长不重复子字符串的长度
        //dp[i]=dp[i-1]+1   dp[i-1]<i-k
        //=i-k    dp[i-1]>=i-k
        int res = 0,max = 0;
        for(int i=0;i<s.length();i++){
            //找与i相等的上一个k
            int k =i-1;//从当前下标往前循环，找
            while(k>=0 && s.charAt(k)!=s.charAt(i))
                k--;
            res = res<i-k?res+1:i-k;
            max = Math.max(res,max);
        }
        return max;
    }
}

代码2：(用这个)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        //记录字符上一次出现位置,为什么128？
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int len = s.length();
        int res =0;
        int start =0;
        //i就是滑动窗口的右边
        for(int i=0;i<len;i++){
            int c = s.charAt(i);
            start = Math.max(start,last[c]+1);
            res = Math.max(res,i-start+1);
            last[c]=i;
        }
        return res;
    }
}

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口
        HashMap<Character, Integer> window = new HashMap<>();
        //开始定义窗口双指针
        int left =0,right=0;
        int res = 0 ;
        while(right<s.length()){
            //获取移入窗口的值
            char c = s.charAt(right);
            right++;
            //窗口更新
            window.put(c,window.getOrDefault(c,0)+1);
            //确定左边是否要收缩
            while (window.get(c)>1){
                //移动左边，窗口缩小
                char c1 = s.charAt(left);
                left++;
                //开始更新窗口内容
                window.put(c1,window.getOrDefault(c1,0)-1);
            }
            res = Math.max(res,right-left);
        }
        //返回
        return res;
    }
}