本文是对解题思路的整理。

题目描述

输入一个字符串（只包含 a ~ z 的字符），求其最长不含重复字符的子字符串的长度。

例如对于 arabcacfr，最长不含重复字符的子字符串为 acfr，长度为 4。

子串 和 子序列 的区别？

子串 是字符串的一部分，该部分是由连续的字符构成的。例如字符串：abc，子串有 a、b、c、ab、bc、abc 以及 空串，共有 $ {\frac{n(n+1)}{2}}+1 = 7 $ 种。

子序列 是也是由字符串中的字符构成的，即从最初序列通过去除某些元素但不破坏余下元素的 相对位置（在前或在后）而形成的新序列。例如字符串：abc，子序列有 a、b、c、ab、ac、bc、abc 以及 空串，共有 $ 2^n = 8 $ 种。

分析

这里使用 DP（Dynamic Programming）的思想。

首先，让 f(i) 表示以第 i 个字符为结尾不重复子串的最长长度；
然后，从左到右扫描字符串中的每个字符，当我们计算得到 f(i) 的时候，其实 f(i + 1) 就已经知道了。因为 f(i) 是依赖 f(i + 1) 的；
下面分两种情况：
- 如果第 i 个字符之前没有出现过，则 f(i) = f(i - 1) + 1，加的这个 1 就表示把当前字符 i 加入到不重复子串中，其长度要增 1；
- 如果第 i 个字符之前出现过，则计算当前第 i 个字符与它上次出现在字符串中的位置的距离 d：
  - 如果 d <= f(i - 1)，则 f(i) = d，（这种情况说明第 i 个字符上次在 f(i - 1) 对应的最长子串中出现过）；
  - 如果 d > f(i - 1)，则 f(i) = f(i - 1) + 1，（这种情况说明第 i 个字符在 f(i - 1) 对应的最长子串之前出现过）。

如何判断第 i 个字符之前有没有出现过？

可以使用 哈希表 或者数组实现。

例如字符串 arabcacfr，如下所示：

字符	a	r	a	b	c	a	c	f	r
索引	0	1	2	3	4	5	6	7	8

f(0) 对应的字符 a 之前没出现过，
- 所以 f(0) = 1；
- 此时 f(0) 对应的子串为 a。
f(1) 对应的字符 r 之前没出现过，
- 所以 f(1) = f(0) + 1 = 2；
- 此时 f(1) 对应的子串为 ar。
f(2) 对应的字符 a 之前出现过，此时需要判断距离 d。
- 首先 d = 2 - 0 = 2；
- 然后，由于 d <= f(2 - 1) = f(1) = 2；
- 所以 f(2) = 2；
- 此时 f(2) 对应的子串为 ra。
f(3) 对应的字符 b 之前没出现过，
- 所以 f(3) = f(2) + 1 = 3;
- 此时 f(3) 对应的子串为 rab。
f(4) 对应的字符 c 之前没出现过，
- 所以 f(4) = f(3) + 1 = 4；
- 此时 f(4) 对应的子串为 rabc。
f(5) 对应的字符 a 之前出现过，此时需要判断距离 d。
- 首先 d = 5 - 2 = 3；
- 然后，由于 d <= f(5 - 1) = f(4) = 4；
- 所以 f(5) = 3；
- 此时 f(5) 对应的子串为 bca。
f(6) 对应的字符 c 之前出现过，此时需要判断距离 d。
- 首先 d = 6 - 4 = 2；
- 然后，由于 d <= f(6 - 1) = f(5) = 3；
- 所以 f(6) = 2；
- 此时 f(6) 对应的子串为 ac。
f(7) 对应的字符 f 之前没出现过，
- 所以 f(7) = f(6) + 1 = 3；
- 此时 f(7) 对应的子串为 acf。
f(8) 对应的字符 r 之前出现过，此时需要判断距离 d。
- 首先 d = 8 - 1 = 7；
- 然后，由于 d > f(8 - 1) = f(7) = 3；
- 所以 f(8) = f(8 - 1) + 1 = f(7) + 1 = 4；
- 此时 f(8) 对应的子串为 acfr。

通过以上的分析后，就可以编写代码了。

代码

 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


public class Solution {
    public static int longestSubstringWithoutDup(String str) {
        if (str == null || str.length() < 1) {
            return 0;
        }

        int curLen = 0;
        int maxLen = 0;
        int[] position = new int[26];
        // Arrays.fill(position,-1);
        for (int i = 0; i < position.length; i++) {
            position[i] = -1;
        }

        for (int curIndex = 0; curIndex < str.length(); curIndex++) {
            int c = str.charAt(curIndex) - 'a';
            int preIndex = position[c];
            // 如果第 i 个字符之前没有出现过 或者 第 i 个字符之前出现过并且 d > f(i - 1)
            // 那么 f(i) = f(i - 1) + 1
            if (preIndex == -1 || curIndex - preIndex > curLen) {
                curLen++;
            } else {
                // 如果第 i 个字符之前出现过，并且 d <= f(i - 1)
                maxLen = Math.max(curLen, maxLen);
                curLen = curIndex - preIndex;
            }
            position[c] = curIndex;
        }
        maxLen = Math.max(curLen, maxLen);
        return maxLen;
    }

剑指 Offer 之最长不含重复字符的子字符串

Contents

题目描述

分析

代码