求字符串中最长无重复字符子串长度

前言

本文介绍一道算法题，求字符串中最长无重复字符子串长度。

正文

题目描述：

给出一个字符串，求字符串中最长无重复字符子串长度。

示例：给出字符串abcdefggddabccef，其中最长子串为abcdefg，长度为7。

注意，子串是指一个字符串中连续的字符组合，不能跳跃字符进行组合。

思路解析

示例给出的字符串abcdefggddabccef包含连续的子串有abcdefg、gd、dabc、cef等，其中最长的为abcdefg。

看到这类的题目之后，第一反应就是从左到右遍历字符串，找最大值即可，过程如下：

• 从下标0开始往左对比，记录不重复字符的个数，此时只有a字符，记录max=1。
• 从下标1开始往左对比，记录不重复字符的个数，此时有ab字符，记录max=2。
• 从下标2开始往左对比，记录不重复字符的个数，此时有abc字符，记录max=3。
• 以此类推，直到遍历到最后，找出最大值即可。

在遍历的时候，不是从某个位置一直往左对比，一直到头的，只要对比到该字符上次出现的位置即可，因此对比终止需要两个因素：

• 当前字符上次出现的位置
• 当前字符前一个位置已经记录的距离

这两个因素产生的位置，那个小，就是本次遍历产生的距离，由这个产生的结果和之前的结果对比，如果是大的则更新最大值。

如上图所示，第22位置的a虽然距离第11位置的a很远，但是中间有两个s重复了，所以22位置的a只能记录距离为5。

代码实现

根据上面思路分析，来看下代码实现：

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.equals("")) {
        return 0;
    }
    char[] str = s.toCharArray();
    int[] map = new int[128];
    for (int i = 0; i < 128; i++) {
        map[i] = -1;
    }
    map[str[0]] = 0;
    int N = str.length;
    int ans = 1;
    int pre = 1;
    for (int i = 1; i < N; i++) {
        int cur = Math.min(i - map[str[i]], pre + 1);
        ans = Math.max(ans, cur);
        map[str[i]] = i;
        pre = cur;
    }
    return ans;
}

声明一个长度为128的数组是因为ASCII码只有128个，足以表示所有的字符了。

根据思路分析里的两个因素分析，可以看到两个因素参数的结果：

• i - map[str[i]]当前元素距离上一个元素的距离
• pre表示上一个元素计算的结果，在pre基础上加上1就是本次计算的结果

在计算出本次产生的子串长度后，要把本次字符出现的位置更新到map数组中，以便后面再次出现对比使用，每次循环结束后，要把cur赋值给pre，也就是更新上一次计算的结果。

这两个因素产生的结果的最小值就是本次计算的结果，拿到这个结果后，再和之前计算的结果ans对比，这两个中的最大值，就是循环遍历到i位置的最长子串的长度值。

在力扣上跑一下看看，打败了100%哈哈~

总结

本文介绍一道算法题，求字符串中最长无重复字符子串长度，关于本题的解法有很多，例如：动态规划、滑动窗口、暴力循环等，本题相对比较简单，这里就不再做过多介绍了。