LeetCodeDay38 —— 无重复字符的最长子串★★

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

描述

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

示例

• 给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
• 给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
• 给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke"是子序列而不是子串。

思路

1. 时间复杂度 O(n^2) 的解法，依次遍历以每个字符开头的子字符串，选择最大的一个。
2. 时间复杂度 O(n) 的解法，双指针标记头尾，使用startIndex和endIndex来标识当前的"无从重复子串"
   1)若当前字符是第一次遍历，则将其添加到集合中，并更新endIndex值。
   2)若当前字符不是第一次遍历，更新maxLength，并移除startIndex对应的数据，然后再更新startIndex值。

class Solution_03_01 {
 public:
  int lengthOfLongestSubstring(string s) {
    if (s.empty()) return 0;
    int ret = 1;
    unordered_map<char, int> mp;
    for (int i = 0; i < s.size(); ++i) {
      int tmp = 1;
      mp.clear();
      mp[s[i]] = 1;
      for (int j = i + 1; j < s.size(); ++j) {
        if (mp.find(s[j]) != mp.end()) break;
        ++tmp;
        mp[s[j]] = 1;
        ret = tmp > ret ? tmp : ret;
      }
    }
    return ret;
  }
};

class Solution_03_02 {
 public:
  int lengthOfLongestSubstring(string s) {
    int ret = 0;
    if (s.empty()) return ret;
    std::unordered_set<char> mSet;
    int size = s.size();
    int startIndex = 0;
    int endIndex = 0;
    while (startIndex < size && endIndex < size && startIndex <= endIndex) {
      if (mSet.find(s[endIndex] == mSet.end()){
        mSet.insert(s[endIndex]);
        ++endIndex;
      } else {
        ret = (endIndex - startIndex) > ret ? (endIndex - startIndex) : ret;
        mSet.erase(s[startIndex]);
        ++startIndex;
      }
    }
    ret = (endIndex - startIndex) > ret ? (endIndex - startIndex) : ret;
    return ret;
  }
};