原题

3.无重复字符的最长子串

题目描述

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

示例

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

解析

方法一：

  • 原理

这是一道经典的动态规划题目，最简单的理解是求出每个字符为结尾不重复的最长子串。步骤如下：

  1. 定义一个数组dp，数组中的第i个字符结尾时的最长子串，这个数组中的每一项默认是s[i]。
  2. 遍历字符串s，计算并填充dp中的每一项。
    2.1 找到s[i]是否存在于dp[i]的字符串中？
    如果存在，返回从右往左数位置r_index，则从dp[i]的r_index开始，和当前s[i]就可以组成新的不重复子串。
    2.2 如果不存在，则直接把当前字符串与之前的子串进行拼接dp[i]=dp[i-1]+s[i]。
  3. 遍历dp数组，寻找最长的字符串即可。
  • 代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def lengthOfLongestSubstring(self, s: str) -> int:
    n = len(s)
    if n<2:
        return n
    # 防止报None
    dp=list(s)
    # 直接从第1个开始
    for i in range(1,n):
        r_index = dp[i-1].rfind(s[i])
        if r_index>-1:
            # 当前字符存在于上一个子串的r_index位
            dp[i]=dp[i-1][r_index+1:]+s[i]
        else:
            # 不存在，直接相加
            dp[i]=dp[i-1]+s[i]
    #  返回最大长度的子串
    return max([len(ss) for ss in dp])

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    if (n < 2) {
        return n;
    }
    String[] dp = new String[n];
    dp[0] = s;
    for (int i = 1; i < n; i++) {
        int r_index = dp[i - 1].lastIndexOf(s.charAt(i));
        if (r_index > -1) {
            dp[i] = dp[i - 1].substring(r_index + 1) + s.charAt(i);
        } else {
            dp[i] = dp[i - 1] + s.charAt(i);
        }
    }
    int maxLength = 0;
    for (String ss : dp) {
        maxLength = Math.max(maxLength, ss.length());
    }
    return maxLength;
}

方法二：

定义了一个数组dp,来保存以每个字符结尾的最长不重复子串，但在这个数组中，真正用到的只有dp[i-1]这一个子串的长度，所以简化一下，只上一次子串的长度last_len。

  • 代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def lengthOfLongestSubstring(self, s: str) -> int:
    if len(s)==0:
        return 0
    max_len = 1
    last_len = 1
    for i in range(1,len(s)):
        max_arr = s[i-last_len:i]
        print(max_arr,s[i])
        r_index = max_arr.rfind(s[i])
        if len(max_arr)>0 and r_index>-1:
            #  存在
            last_len = last_len-r_index
        else:
            # 不存在
            last_len += 1
            max_len = max(last_len, max_len)
    return max_len

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lengthOfLongestSubstring(String s) {
    if (s.isEmpty()) {
        return 0;
    }
    int maxLength = 1;
    int lastLength = 1;
    for (int i = 1; i < s.length(); i++) {
        String maxArr = s.substring(i - lastLength, i);
        System.out.println(maxArr + " " + s.charAt(i));
        int rIndex = maxArr.lastIndexOf(s.charAt(i));
        if (maxArr.length() > 0 && rIndex > -1) {
            // 存在
            lastLength = lastLength - rIndex;
        } else {
            // 不存在
            lastLength++;
            maxLength = Math.max(lastLength, maxLength);
        }
    }
    return maxLength;
}