一、题目描述

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

示例一

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

示例二

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

示例三

1
2
3
4
5
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

二、解决方案

1、暴力

遍历指定字符串，不断扩大子串的范围，在这个过程中判断扩大子串指针处的字符是否在当前子串中已经存在，如果存在则跳过当前循环，因为子串中已经出现重复字符，没有必要继续向下找其他的重复字符了，之后更新子串的起始位置，重新向后遍历字符串来扩大子串的范围，直到遇到重复字符为止。

这种多个循环不停遍历会有一些子串重复判断，比如字符串 bacda，在遍历到第二个 a 时确定重复字符，此时最长子串为 bacd；之后起始指针加 1，在遍历到第二个 a 时确定重复字符，此时最长子串为 acd，但这次遍历其实是没有必要的，因为 acd 长度不可能大于 bacd

需要两个循环来确定子串起始和结束位置，另外还需要一个循环判断字符是否在子串中存在，时间复杂度为 O(n3)

2、滑动窗口

滑动窗口是一种常用的算法技巧，通常用于解决数组或字符串相关的优化问题。它特别适用于需要在连续子序列或子字符串上操作的问题，并且可以显著减少不必要的计算。

滑动窗口的基本思想

滑动窗口的核心思想是保持一个窗口，这个窗口的大小可能固定也可能不固定，根据具体问题来决定。我们通过两个指针（例如：start 和 end）来表示窗口的边界，这两个指针都在数组或字符串上滑动。随着遍历过程，我们会调整窗口的大小和位置，以找到满足条件的最优解。

时间复杂度分析：在 O(2n) = O(n)。在最糟糕的情况下，每个字符都将被 i 和 j 访问两次。

3、优化的滑动窗口

将窗口中的字符存储在 Set 或 Map 中。

三、代码实现

1、暴力破解

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
/**
 * <p>暴力破解
 *
 * <p>三个 for 循环遍历，找无重复字符的最长子串
 */
public int lengthOfLongestSubstring(String s) {
    int result = 0;
    if (s == null || s.isEmpty()) {
        return result;
    }
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 1; j <= s.length(); j++) {
            String subStr = s.substring(i, j - 1);
            String repeatStr = s.substring(j - 1, j);
            if (subStr.contains(repeatStr)) {
                // 当某个子串中的最后一个字符在子串中重复时，跳过当前循环
                break;
            } else {
                // 如果不重复时，将 result 和 j-i 中更大的赋值给 result，相当于更新了不重复子串的最大长度
                result = Math.max(j - i, result);
            }
        }
    }
    return result;
}

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
/**
 * <p>滑动窗口
 * <p>优化掉暴力破解遍历过程中不需要重复判断的部分
 */
public int lengthOfLongestSubstring2(String s) {
    int result = 0;
    if (s.length() == 1) {
        return 1;
    }
    for (int i = 0, j = 1; i < s.length() && j < s.length(); ) {
        // i 和 j 来确定窗口的起始位置和结束为止
        String subStr = s.substring(i, j);  
        // judgeRepeatSingleStr 为待判断是否在窗口中有重复的字符  
        String judgeRepeatSingleStr = s.substring(j, j + 1);  
        int index = subStr.indexOf(judgeRepeatSingleStr);
        if (index != -1) {
            // 当有重复时，将 i 向后移动 index + 1，即窗口中出现重复的字符的下一个字符
            i = i + index + 1;
        } else {
            j++;
            result = Math.max(j - i, result);
        }
    }
    return result;
}

3、优化版滑动窗口

3.1 使用 Set 存储窗口中字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * <p>滑动窗口
 * <p>优化掉暴力破解遍历过程中不需要重复判断的部分
 * <p>优化版
 */
public int lengthOfLongestSubstring3(String s) {
    int result = 0;
    int i = 0, j = 0;
    // set 用来存放窗口中的字符
    Set<Character> set = new HashSet<>();
    while (i < s.length() && j < s.length()) {
        // 当 set 中包含当前 j 遍历字符时，从 set 中移除 i 位置的字符，之后 i 增加，j 不变，直到 set 中没有当前 j 遍历的字符为止
        if (set.contains(s.charAt(j))) {
            set.remove(s.charAt(i++));
        } else {
            // 当 set 中不包含当前 j 遍历字符时，将该处的字符添加到 set 中，并更新 result 的值
            set.add(s.charAt(j++));
            result = Math.max(j - i, result);
        }
    }
    return result;
}

空间复杂度分析：O(min(m, n))，需要 O(k) 的空间，其中 k 表示 Set 的大小。而 Set 的大小取决于字符串的长度 n 以及字符集的大小 m（字符串 abccba 的字符集为 {a, b, c}）

3.2 使用 Map 存储字符和位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * <p>滑动窗口
 * <p>使用 map 来存储字符及其位置
 */
public int lengthOfLongestSubstring4(String s) {
    int result = 0;
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0, j = 0; i < s.length() && j < s.length(); j++) {
        char c = s.charAt(j);
        if (map.containsKey(c)) {
            // 如果 map 中包含当前字符，则窗口子串中有重复字符  
            // 获取窗口中重复字符位置，将窗口左侧指针移动到重复字符的下一个位置  
            // 这里需要处理从 map 中获取到了窗口外的元素的情况  
            // 获取到窗口外的元素时，不需要重置窗口位置，比如遍历到 tmmzuxt 字符的第二个 t 时，会获取第一个 t 的位置
            i = Math.max(map.get(c) + 1, i);
        }
        // 将遍历元素及其位置存放到 map 中
        map.put(c, j);
        result = Math.max(j - i + 1, result);
    }
    return result;
}

四、测试

1、生成测试数据

生成数据到 csv 文件

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
@Slf4j
class CsvTestDataGenerator {

    /**
     * 测试数据生成路径
     */
    public static final String TEST_DATA_PATH = "src/test/resources/csv/problem/NO_0003/";

    /**
     * 测试数据生成数量
     */
//    public static final int TEST_DATA_SIZE = 10_000;
//    public static final int TEST_DATA_SIZE = 100_000;
//    public static final int TEST_DATA_SIZE = 1_000_000;
    public static final int TEST_DATA_SIZE = 5_000_000;

    public static void main(String[] args) throws IOException {

        Solution solution = new Solution();

        List<Data> list = new ArrayList<>(TEST_DATA_SIZE);
        for (int i = 0; i < TEST_DATA_SIZE; i++) {
            String string = RandomStringUtils.randomAlphabetic(4, 32).toLowerCase();
            list.add(new Data(string, solution.lengthOfLongestSubstring4(string)));
        }

        CsvWriteConfig csvWriteConfig = CsvWriteConfig.defaultConfig();

        File file = ResourceUtils.getFile(TEST_DATA_PATH + "test_data_" + TEST_DATA_SIZE + ".csv");

		try (FileWriter fileWriter = new FileWriter(file);
             CsvWriter csvWriter = new CsvWriter(fileWriter, csvWriteConfig)) {

            csvWriter.writeBeans(list);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
		
	@lombok.Data
	@Accessors(chain = true)
	@NoArgsConstructor
	@AllArgsConstructor
	static class Data {
	
		private String string;
		
		private int expect;
	}
		
}

2、Junit5 测试用例

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
@Slf4j
class SpeedTest {

	private static final String TEST_DATA_CLASS_PATH = ResourceUtils.CLASSPATH_URL_PREFIX + "csv/problem/NO_0003/test_data_5000000.csv";

    private final Solution solution = new Solution();

    private static List<CsvTestDataGenerator.Data> testData;

    @BeforeAll
    public static void initTestData() throws IOException {

        CsvReadConfig csvReadConfig = CsvReadConfig.defaultConfig();
        csvReadConfig.setHeaderLineNo(0).setBeginLineNo(0);

        try (InputStreamReader fileReader = new FileReader(ResourceUtils.getFile(TEST_DATA_CLASS_PATH));
             CsvReader reader = CsvUtil.getReader(fileReader, csvReadConfig);) {

            CsvData csvData = reader.read();

            testData = csvData.getRows().stream().map(row -> row.toBean(CsvTestDataGenerator.Data.class)).toList();
        } catch (FileNotFoundException e) {
            throw new RuntimeException(e);
        }
    }

    @Test
    void speedTest_lengthOfLongestSubstring() {
        long start, end;

        start = System.currentTimeMillis();
        for (CsvTestDataGenerator.Data data : testData) {
            int expect = solution.lengthOfLongestSubstring(data.getString());
            Assertions.assertEquals(data.getExpect(), expect);
        }
        end = System.currentTimeMillis();
        log.info("lengthOfLongestSubstring 处理 {} 条数据，用时 {} ms", testData.size(), end - start);
    }

    @Test
    void speedTest_lengthOfLongestSubstring2() {
        long start, end;
        start = System.currentTimeMillis();
        for (CsvTestDataGenerator.Data data : testData) {
            int expect = solution.lengthOfLongestSubstring2(data.getString());
            Assertions.assertEquals(data.getExpect(), expect);
        }
        end = System.currentTimeMillis();
        log.info("lengthOfLongestSubstring2 处理 {} 条数据，用时 {} ms", testData.size(), end - start);
    }

    @Test
    void speedTest_lengthOfLongestSubstring3() {
        long start, end;
        start = System.currentTimeMillis();
        for (CsvTestDataGenerator.Data data : testData) {
            int expect = solution.lengthOfLongestSubstring3(data.getString());
            Assertions.assertEquals(data.getExpect(), expect);
        }
        end = System.currentTimeMillis();
        log.info("lengthOfLongestSubstring3 处理 {} 条数据，用时 {} ms", testData.size(), end - start);
    }

    @Test
    void speedTest_lengthOfLongestSubstring4() {
        long start, end;
        start = System.currentTimeMillis();
        for (CsvTestDataGenerator.Data data : testData) {
            int expect = solution.lengthOfLongestSubstring4(data.getString());
            Assertions.assertEquals(data.getExpect(), expect);
        }
        end = System.currentTimeMillis();
        log.info("lengthOfLongestSubstring4 处理 {} 条数据，用时 {} ms", testData.size(), end - start);
    }

}

输出如下：

1
2
3
4
[15:40:42.710][INFO ] cn.z2huo.leetcode.problem.NO_0003.SpeedTest:60 speedTest_lengthOfLongestSubstring - lengthOfLongestSubstring 处理 5000000 条数据，用时 7917 ms
[15:40:44.975][INFO ] cn.z2huo.leetcode.problem.NO_0003.SpeedTest:72 speedTest_lengthOfLongestSubstring2 - lengthOfLongestSubstring2 处理 5000000 条数据，用时 2251 ms
[15:40:46.505][INFO ] cn.z2huo.leetcode.problem.NO_0003.SpeedTest:84 speedTest_lengthOfLongestSubstring3 - lengthOfLongestSubstring3 处理 5000000 条数据，用时 1528 ms
[15:40:47.920][INFO ] cn.z2huo.leetcode.problem.NO_0003.SpeedTest:96 speedTest_lengthOfLongestSubstring4 - lengthOfLongestSubstring4 处理 5000000 条数据，用时 1414 ms

相关链接

OB tags

#LeetCode #算法