8.无重复字符的最长子串

3. 无重复字符的最长子串

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

题目思路

核心思想：滑动窗口

要点：

1. 用 begin 和 end 表示子串开始和结束位置
2. 用 hash 表检查重复字符「key：字符，value：字符下标」
3. 从左向右查看每个字符, 如果:
   1. 没遇到重复字符，调整 end++
   2. 遇到重复的字符，调整 begin（调整begin到重复字符的下一位，如果重复字符的下一位<begin，则仍然取begin，因为begin不可能倒退）
   3. 将当前字符放入 hash 表，hash表的键表示当前字符，值表示当前字符的索引
4. end - begin + 1 是当前子串长度

题目代码

/**
 * 使用链表充当子串，如果出现重复字符，则不断删除链表头中的字符，直到不出现重复，时间复杂度高
 * @param s
 * @return
 */
public int lengthOfLongestSubstring(String s) {
    // 参数校验
    if (s == null || s.isEmpty()) {
        return 0;
    }
    int right = 0; // 滑动窗口的右边界
    int max = 0; // 最长子串
    // 这个list链表就相当于连续子串
    LinkedList<Character> list = new LinkedList<>();
    while (right < s.length()) {
        char c = s.charAt(right);
        // 如果连续子串中出现重复的字符，则一直删除子串头的字符，直到不出现重复
        while (list.contains(c)) {
            list.removeFirst();
        }
        // 将当前字符添加到子串中
        list.addLast(c);
        right++;
        // 记录最长子串
        max = Math.max(list.size(), max);
    }
    return max;
}

//使用map检查是否有重复字符
public int lengthOfLongestSubstring(String s) {
    //使用map检查是否有重复字符，其中key-字符 value-字符下标
    Map<Character, Integer> map = new HashMap<>();
    int begin = 0;
    //定义maxLength变量记录最长子串
    int maxLength = 0;
    for (int end = 0; end < s.length(); end++) {
        //遍历字符串，获取每一个字符
        char ch = s.charAt(end);
        //如果当前字符存在map中，说明重复了
        if (map.containsKey(ch)) { //重复
            //将begin修改为在begin和end范围内，重复字符的下一个字符索引
            // 如果重复字符的下标比begin还小，则还取begin，因为begin不能倒退
            begin = Math.max(begin, map.get(ch) + 1);
            //将重复字符的下标修改
            map.put(ch, end);
        } else { //不重复
            //将字符和字符下标放入map集合中
            map.put(ch, end);
        }
        //最大长度即为每次循环得到的字符串的最大值
        maxLength = Math.max(maxLength, end - begin + 1);
    }
    //返回无重复最大子串长度
    return maxLength;
}

// 使用数组代替哈希表
public int lengthOfLongestSubstring2(String s) {
    //使用数组检查是否有重复字符，其中 索引-字符 值-字符下标
    int[] map = new int[128];
    // 初始全部填充为-1，因为字符下标不可能为-1
    Arrays.fill(map, -1);
    int begin = 0;
    //定义maxLength变量记录最长子串
    int maxLength = 0;
    for (int end = 0; end < s.length(); end++) {
        //遍历字符串，获取每一个字符
        char ch = s.charAt(end);
        //如果当前字符存在map中，说明重复了
        if (map[ch] != -1) { //之前出现过，重复 
            //将begin修改为在begin和end范围内，重复字符的下一个字符索引
            begin = Math.max(begin, map[ch] + 1);
            //将重复字符的下标修改
            map[ch] = end;
        } else { //不重复
            //将字符和字符下标放入map集合中
            map[ch] = end;
        }
        //最大长度即为每次循环得到的字符串的最大值
        maxLength = Math.max(maxLength, end - begin + 1);
    }
    //返回无重复最大子串长度
    return maxLength;
}