无重复字符的最长子串

题面

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

示例 1:

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

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

示例 3:

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

提示：

0 <= s.length <= 5 104

• s 由英文字母、数字、符号和空格组成

分析

• 可以使用同向指针来解决

• 两个指针最开始都指向数组起始，不断移动右指针，当遇到某个字符的数量已经为 1 时，此时已经会导致重复；因此更新最长不重复子串的长度；同时向右移动左指针，直到右指针指向的字符数量为 0；如此循环往复

• 注意最后要再更新一次最长长度，因为当全程无重复/ 末尾无重复 / 中间重复但是末尾更长时不会触发结果更新逻辑

• 代码实现

  class Solution {
  public:
      int lengthOfLongestSubstring(string s) {
          std::unordered_map<char, int> count;
          if (s.size() == 1)
              return 1;
          int result = 0;
          int i = 0, j = 0;
          for (; j < s.size(); j++) {
              if (count[s[j]] >= 1) {
                  result = max(j - i, result);
                  while (count[s[j]] >= 1) {
                      count[s[i]] -= 1;
                      i++;
                  }
              }
              count[s[j]] += 1;
          }
          result = max(j - i, result);
          return result;
      }
  };

• 优化逻辑

  • i 逐次移动，效率较低，可以直接跳到 max(i, 重复字符的最后位置+1)，减少循环；具体可以改为维护字符最后一次出现的位置
  • 同时，由于字符的 ASCII 范围有限（0-127），可以使用数组代替哈希表

• 代码实现

  #include <string>
  #include <algorithm>
  #include <vector>
  using namespace std;
  
  class Solution {
  public:
      int lengthOfLongestSubstring(string s) {
          vector<int> last_pos(128, -1);
          int result = 0;
          int i = 0;
          
          for (int j = 0; j < s.size(); j++) {
              if (last_pos[s[j]] != -1) {
                  i = max(i, last_pos[s[j]] + 1);
              }
              last_pos[s[j]] = j;
              result = max(result, j - i + 1);
          }
          
          return result;
      }
  };

• 本题代码

  class Solution {
  public:
      int lengthOfLongestSubstring(string s) {
          int n = s.size();
          if (n == 0) return 0; // 补充空字符串边界条件
          if (n == 1) return 1; // 保留原代码的单字符判断
          
          unordered_map<char, int> count; // 窗口内字符计数
          int result = 0;
          
          // 标准滑动窗口模板：l=左边界，r=右边界，外层扩展r
          for (int l = 0, r = 0; r < n; r++) {
              // 当前考虑的元素：s[r]，先加入计数
              count[s[r]]++;
              
              // 内层循环：检查区间[l,r]是否符合题意（无重复字符），不符合则收缩l
              while (l <= r && count[s[r]] > 1) { // 当当前字符计数>1，说明窗口内有重复
                  // 收缩左边界：移除左边界字符的计数，l右移
                  count[s[l]]--;
                  l++;
              }
              
              // 此时区间[l,r]符合题意（无重复），统计最长长度
              result = max(result, r - l + 1);
          }
          
          return result;
      }
  };