面试算法16：不含重复字符的最长子字符串

题目

输入一个字符串，求该字符串中不含重复字符的最长子字符串的长度。例如，输入字符串"babcca"，其最长的不含重复字符的子字符串是"abc"，长度为3。

分析

在字符串"babcca"中找最长的不含重复字符的子字符串时，两个指针都初始化指向第1个字符’b’，此时子字符串为"b"，不含重复字符。于是向右移动第2个指针使其指向字符’a’，此时子字符串为"ba"，仍然不含重复字符。于是再次向右移动第2个指针使其指向字符’b’。
如果两个指针之间的子字符串中包含重复的字符，则可以向右移动第1个指针，删除子字符串中最左边的字符。如果删除最左边的字符之后仍然包含重复的字符，则继续向右移动第1个指针删除最左边的字符。两个指针之间的字符串是"bab"，有重复出现的字符，于是向右移动第1个指针使其指向字符’a’。
如果删除最左边的字符之后不再包含重复的字符，就可以向右移动第2个指针，在子字符串的右边添加新的字符。此时两个指针之间的字符串是"ab"，没有重复出现的字符，于是向右移动第2个指针使其指向字符’c’，得到最长的不含重复字符的子字符串。
由于这个题目没有说明字符串中只包含英文字母，那么就有可能包含数字或其他字符，因此字符就可能不止26个。假设字符串中只包含ASCII码的字符。由于ASCII码总共有256个字符，因此用来模拟哈希表的数组的长度就是256。

解

public class Test {
    public static void main(String[] args) {
        int result = lengthOfLongestSubstring("babcca");
        System.out.println(result);
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }

        int[] counts = new int[256];
        int i = 0;
        int j = -1;
        int longest = 1;// 关键，历史中最大长度
        for (; i < s.length(); i++) {

            counts[s.charAt(i)]++;
            while (hasGreaterThan1(counts)) {
                ++j;
                counts[s.charAt(j)]--;
            }

            longest = Math.max(i - j, longest);
        }

        return longest;
    }

    private static boolean hasGreaterThan1(int[] counts) {
        for (int count : counts) {
            if (count > 1) {
                return true;
            }
        }

        return false;
    }
}
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

分析

我们真正关心的是哈希表中有没有比1大的数字，因为如果有大于1的数字就说明子数组中包含重复的数字。可以定义一个变量countDup来存储哈希表中大于1的数字的个数，即子字符串中重复字符的个数。每次向右移动第2个指针使子字符串包含更多字符时都会把哈希表中对应的数字加1。当一个字符对应的数字从1变成2时，表示该字符重复出现了，因此变量countDup加1。
当向右移动第1个指针删除子字符串中最左边的字符时，都会把哈希表中对应的数字减1。当一个字符对应的数字由2变成1时，该字符不再重复出现，因此变量countDup减1。

解

public class Test {
    public static void main(String[] args) {
        int result = lengthOfLongestSubstring("babcca");
        System.out.println(result);
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }

        int[] counts = new int[256];
        int i = 0;
        int j = -1;
        int longest = 1;
        int countDup = 0;
        for (; i < s.length(); ++i) {
            counts[s.charAt(i)]++;
            if (counts[s.charAt(i)] == 2) {
                countDup++;
            }

            while (countDup > 0) {
                ++j;
                counts[s.charAt(j)]--;
                if (counts[s.charAt(j)] == 1) {
                    countDup--;
                }
            }

            longest = Math.max(i - j, longest);
        }

        return longest;
    }
}
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