来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

描述

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

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

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

示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

题解

滑动窗口

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         int n = s.length(), ans = 0, i = 0, j = 0;
  4.         Set<Character> set = new HashSet<>();
  5.         while (i < n && j < n) {
  6.             if (!set.contains(s.charAt(j))) {
  7.                 set.add(s.charAt(j++));
  8.                 ans = Math.max(ans, j - i);
  9.             } else {
  10.                 set.remove(s.charAt(i++));
  11.             }
  12.         }
  14.         return ans;
  15.     }
  16. }

复杂度分析

  • 时间复杂度：3. 无重复字符的最长子串(Longest Substring Without Repeating Characters) - 图1，在最糟糕的情况下，每个字符都将被i和j访问；
  • 空间复杂度：3. 无重复字符的最长子串(Longest Substring Without Repeating Characters) - 图2。滑动窗口需要3. 无重复字符的最长子串(Longest Substring Without Repeating Characters) - 图3的空间，其中k表示Set的大小。而Set的大小取决于字符串n的大小以及字符集m的大小；

优化滑动窗口

HashMap

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         int n = s.length(), ans = 0;
  4.         Map<Character, Integer> map = new HashMap<>();
  5.         for (int i = 0, j = 0; j < n; j++) {
  6.             if (map.containsKey(s.charAt(j))) {
  7.                 i = Math.max(i, map.get(s.charAt(j)));
  8.             }
  9.             map.put(s.charAt(j), j + 1);
  10.             ans = Math.max(ans, j - i + 1);
  11.         }
  13.         return ans;
  14.     }
  15. }

Array

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         int ans = 0, n = s.length();
  4.         int[] index = new int[128];
  5.         for (int i = 0, j = 0; j < n; j++) {
  6.             i = Math.max(i, index[s.charAt(j)]);
  7.             ans = Math.max(ans, j - i + 1);
  8.             index[s.charAt(j)] = j + 1;
  9.         }
  10.         return ans;
  11.     }
  12. }

复杂度分析

  • 时间复杂度：3. 无重复字符的最长子串(Longest Substring Without Repeating Characters) - 图4，索引j将会迭代n次。
  • 空间复杂度（HashMap）：3. 无重复字符的最长子串(Longest Substring Without Repeating Characters) - 图5，与之前的方法相同。
  • 空间复杂度（Table）：3. 无重复字符的最长子串(Longest Substring Without Repeating Characters) - 图6，m是字符集的大小。