3.无重复字符的最长子串(Longest Substring Without Repeating Characters)M

英文题目

• Given a string s, find the length of the longest substring without repeating characters.

• Example 1:

• Input: s = "abcabcbb"
  Output: 3
  Explanation: The answer is "abc", with the length of 3.
  

• Example 2:

• Input: s = "bbbbb"
  Output: 1
  Explanation: The answer is "b", with the length of 1.
  

• Example 3:

• Input: s = "pwwkew"
  Output: 3
  Explanation: The answer is "wke", with the length of 3.
  

• Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

• Example 4:

• Input: s = ""
  Output: 0
  

• Constraints:

• 0 <= s.length <= 5 * 10^4

• s consists of English letters, digits, symbols and spaces.

中文题目

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

• 示例 1:

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

• 示例 2:

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

• 示例 3:

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

滑动窗口

• 参考：滑动窗口

• 初始化集合lookup

• 遍历每个字符

  • 不断地判断当前字符是否存在lookup集合中，若存在则去除窗口左边字符，直到当前字符不在集合中
  • 把该字符添加到集合中
  • 使用集合的元素数量更新最大集合长度

• 时间复杂度O(n)

  # python: 时间 64 ms, 击败 76.6%; 内存 16 MB, 击败 48.28%
  class Solution:
      def lengthOfLongestSubstring(self, s: str) -> int:
          if not s:
              return 0
          lookup = set()
          left, maxLen = 0, 0
          # right即为窗口右边界
          for right in range(len(s)):
              while s[right] in lookup:
                  lookup.remove(s[left])
                  left += 1
              lookup.add(s[right])
              maxLen = max(maxLen, len(lookup))
          return maxLen
  

  // C++: 时间 40 ms, 击败 15.41%; 内存 13.1 MB, 击败 10.59%
  class Solution {
  public:
      int lengthOfLongestSubstring(string s) {
          if (s.size() == 0) {
              return 0;
          }
          set<char> lookup;
          // 注意要定义成 unsigned long，否则编译不过
          unsigned long maxLen = 0; 
          int left = 0;
          for (int right = 0; right < s.size(); ++right) {
              while (lookup.find(s[right]) != lookup.end()) {
                  lookup.erase(s[left]);
                  ++left;
              }
              lookup.insert(s[right]);
              max_len = std::max(maxLen, lookup.size());
          }
          return max_len;
      }
  };
  

  // java: 时间 6 ms, 击败 47.49%; 内存 42.6 MB, 击败 25.29%
  class Solution {
      public int lengthOfLongestSubstring(String s) {
          if (s.length() == 0) {
              return 0;
          }
          Set<Character> lookup = new HashSet<>();
          int left = 0, maxLen = 0;
          for (int right = 0; right < s.length(); ++right) {
              while (lookup.contains(s.charAt(right))) {
                  lookup.remove(s.charAt(left));
                  ++left;
              }
              lookup.add(s.charAt(right));
              maxLen = Math.max(maxLen, lookup.size());
          }
          return maxLen;
      }
  }
  

  // Go：时间 12 ms, 击败 40.73%; 内存 2.4 MB, 击败 78.98%
  func lengthOfLongestSubstring(s string) int {
      if len(s) == 0 {
          return 0
      }
      lookup := map[byte]bool{}
      left, maxLen := 0, 0
      for right := range s {
          for ; left < right; left++ { // 注意go里的循环
              if _, ok := lookup[s[right]]; !ok {
                  break
              }
              delete(lookup, s[left])
          }
          lookup[s[right]] = true
          maxLen = maxInt(len(lookup), maxLen)
      }
      return maxLen
  }
  
  func maxInt(a, b int) int {
      if a >= b {
          return a
      }
      return b
  }
  

  // javascript: 时间 80 ms, 击败 73.96%; 内存 45.7 MB, 击败 48.40%
  /**
   * @param {string} s
   * @return {number}
   */
  var lengthOfLongestSubstring = function(s) {
      if (s.length == 0) {
          return 0;
      }
      const lookup = new Set();
      let left = 0, maxLen = 0;
      for (let right = 0; right < s.length; ++right) {
          while (lookup.has(s.charAt(right))) {
              lookup.delete(s.charAt(left));
              ++left;
          }
          lookup.add(s.charAt(right));
          maxLen = Math.max(maxLen, lookup.size);
      }
      return maxLen;
  };