找出字符串中不含重复字符的最长子串的长度_程序猿蛋蛋哥的专栏文章_微信文章

1. 题目

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

示例1：
输入："abcabcbb"
输出：3
解释：因为无重复字符的最长子串是："abc"，所以其长度为3

示例2：
输入："bbbbb"
输出：1
解释：因为无重复字符的最长子串是："b"，所以其长度为1

示例3：
输入："pwwkew"
输出：3
解释：因为无重复字符的最长子串是："wke"或"kew"，所以其长度为3
注意：必须是子串的长度，子串是连续的字符，中间不能跳跃字符，如"pwke"是一个子系列，不是子串。

2. 解题思路

2.1 思路一：滑动窗口

窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即[i, j)（左闭，右开），而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。

例如：我们将[i, j)向右滑动1个元素，则它将变为[i+1, j+1)（左闭，右开）
用HashSet存储当前处于窗口[i, j)(最初 j = i)中的字符，然后我们向右滑动索引j，如果它不在HashSet中，我们会继续滑动j，直到s[j]已经存在于HashSet中，此时没有重复的最长子字符串将会以索引i开头

用HashSet存放当前处于滑动窗口中的字符，初始HashSet为空。
窗口的左边i不动，右边j向右滑动，依次遍历字符：j为指向字符的索引。
当j = 0时，遍历字符p，加入HashSet -- [p]，则目前无重复字符的最大子串长度maxSubLength = 1
当j = 1时，遍历字符w，加入HashSet -- [p, w]，则maxSubLength = 2

当j = 2时，遍历字符w，此时HashSet中已包含重复字符w，
则窗口的左边i向右滑，右边j不动，HashSet依次删除索引i所指向的字符，直到HashSet不再包含该字符w，
然后重新将遍历字符w加入HashSet中，启动窗口j继续右滑。

窗口的左边i不动，右边j继续向右滑动，依次遍历字符：j为指向字符的索引
当j = 3时，遍历字符k，加入HashSet -- [w k]
当j = 4时，遍历字符e，加入HashSet -- [w k e]，则此时maxSubLength = 3

当j = 5时，遍历字符w，此时HashSet中已包含重复字符w，
则窗口的左边i向右滑，右边j不动，HashSet依次删除索引i所指向的字符，直到HashSet不再包含该字符w，
然后重新将遍历字符w加入HashSet中，启动窗口j右滑。
结束，则maxSubLength = 3

代码实现：

public static int lengthOfLongestSubstring(String s) {
    if (s == null || "".equals(s)) {
        return 0;
    }
    int n = s.length();
    Set<Character> set = new HashSet<>();
    int maxLength = 0;
    int i = 0;
    int j = 0;
    while (i < n && j < n) {
        if (!set.contains(s.charAt(j))) {
            set.add(s.charAt(j++));
            maxLength = Math.max(j - i, maxLength);
        } else {
            set.remove(s.charAt(i++));
        }
    }
    return maxLength;
}
复制代码

2.2 思路二：优化的滑动窗口

针对上述的滑动窗口方法，不使用集合来判断一个字符是否存在，而定义字符到索引的映射map。当找到重复字符时，可以立即跳过该窗口。

如果在[i, j)范围内有与s[j]重复的字符，索引为j'，即[i, ... j', ... j)，
我们不需要逐渐增加i，可以直接跳过[i, j']范围内的所有元素，并将i变为j' + 1

举例： s = "pwwkew"，当 j = 2时，窗口[0, 2)范围内有与s[2]重复的字符w，索引为1(j' = 1)，我们可以直接跳过[0, 1]范围内的所有元素，将i变为2(j' + 1)

代码实现：

public static int lengthOfLongestSubstring(String s) {
  if (s == null || "".equals(s)) {
		return 0;
	}
	int n = s.length();
	Map<Character, Integer> map = new HashMap<>(16);
	int maxLength = 0;
	for (int i = 0,j = 0; j < n; j++) {
		if (map.containsKey(s.charAt(j))) {
			i = Math.max(map.get(s.charAt(j)), i);
		}
		maxLength = Math.max(maxLength, j - i + 1);
		map.put(s.charAt(j), j + 1);
	}
	return maxLength;
}
复制代码

2.3 思路三：使用列表List存储不重复字符

依次遍历字符串 s 中的每次字符，若不是重复字符，加入一个列表list中，若是重复字符，则删除列表list中该重复字符以及前面的所有字符，然后再将该重复字符加入此列表list中。

在遍历的过程中统计出列表list中存储的最大字符个数，即为字符串 s 中不含重复字符的最长子串的长度。

代码实现

public static int lengthOfLongestSubstring(String s) {
	if (s == null || "".equals(s)) {
		return 0;
	}
	List<Character> list = new ArrayList<>();
	int n = s.length();
	int maxLength = 0;
	for (int i = 0; i < n; i++) {
		int index = list.indexOf(s.charAt(i));
		if (index == -1) {
			list.add(s.charAt(i));
			maxLength = Math.max(list.size(), maxLength);
		} else {
			for (int j = index; j >= 0; j--) {
				list.remove(j);
			}
			list.add(s.charAt(i));
		}
	}
	return maxLength;
}
复制代码