九章算法 | Amazon面试题：最长无重复字符的子串

给定一个字符串，请找出其中无重复字符的最长子字符串。

在线评测地址：LintCode 领扣

样例 1:

输入: "abcabcbb"
输出: 3
解释: 最长子串是 "abc". 

样例 2:

输入: "bbbbb"
输出: 1
解释: 最长子串是 "b". 

解题思路

• 暴力解法时间复杂度较高，会达到O(n^3)，故而采取滑动窗口的方法降低时间复杂度。
• 我们使用两个指针表示字符串中的某个子串的左右边界。每步操作中，右指针向右移动一位，然后不断移动左指针，直到这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着以右指针结束的，不包含重复字符的最长子串。我们记录下这个子串的长度。
• 在枚举结束后，我们找到的最长的子串的长度即为答案。

算法流程

• ​window​是滑窗内字符的集合，初始化为空。从前向后移动滑窗，同时更新当前子串长度​cur_len​和最长子串长度​max_len​。当滑窗右端移动到字符​ch​：
  • 如果​ch​已存在​window​中，那么从滑窗的左端起删除字符，直到删除​ch​。每删除一个字符​cur_len​减1。
  • 将​ch​添加到​window​中，​cur_len​加1。
  • 更新最长子串长度​max_len​。
• 返回​max_len​。

复杂度分析

• 时间复杂度：O(n)，​n​为字符串​s​长度。左指针和右指针分别会遍历整个字符串一次。
• 空间复杂度：O(|Σ|)。Σ为字符串​s​中出现的字符集。由于我们使用哈希表来存储子串的字符，因此空间复杂度为O(|Σ|)。

代码

class Solution {

    public int lengthOfLongestSubstring(String s) {

        if (s == null) {
            return 0;
        }

        HashSet<Character> window = new HashSet<Character>();

        int left = 0, curLen = 0, maxLen = 0;
        char[] sc = s.toCharArray();

        for (char ch: sc) {

            // 从前向后删除，直到删除了ch
            while (window.contains(ch)) {

                window.remove(sc[left]);
                left ++;
                curLen --;
            }
            // 添加ch
            window.add(ch);
            curLen ++;
            // 更新长度
            maxLen = Math.max(maxLen, curLen);
        }
        return maxLen;
    }
}

更多题解参考：

九章算法