#3 无重复字符的最长子串(滑动窗口)

3. 无重复字符的最长子串 - 力扣（LeetCode）

指定一个窗口，窗口覆盖最长非重复子串。

迭代过程：向后探测一步。如果探测字符在窗口中，则寻找该位置，将窗口起点滑动到该位置后面。将窗口结尾推动一步，此时窗口字符串有效，更新最大长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
      if(!s.size()) return 0;
      int i = 0;
      int j = 1;
      int max = 1;
      string tmp;
      while (j < s.size()) {
          tmp = s.substr(i, j - i);
          if (tmp.find(s[j]) != string::npos)
              i += tmp.find(s[j])+1;
          //sub str valid
          j++;
          tmp = s.substr(i, j - i);
          if (tmp.size() > max) max = tmp.size();
      }
      return max;
  }
};

常数优化：

注意如果探测字符在窗口中，意味着这窗口长度一定比之前更短了，对更新最大长度没有贡献。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
      if(!s.size()) return 0;
      int i = 0;
      int j = 1;
      int max = 1;
      string tmp;
      while (j < s.size()) {
          tmp = s.substr(i, j - i);
          if (tmp.find(s[j]) != string::npos) {
              i += tmp.find(s[j])+1;
              // skip update
              j++;
              continue;
          }
          //sub str valid
          j++;
          tmp = s.substr(i, j - i);
          if (tmp.size() > max) max = tmp.size();
      }
      return max;
  }
};